Information and coding theory
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
58 records · Search and filter
- CS-23 Capacity of the General Discrete Memoryless Relay Channel
- CS-39 Asymptotic tightness of the binary Gilbert–Varshamov bound
- CS-51 Capacity of the Binary Deletion Channel
- CS-55 Quantum versus Classical Communication Complexity of Total Functions
- CS-56 Reliability Function of the Binary Symmetric Channel Below the Critical Rate
- CS-58 Constant-Query Locally Decodable Codes with Polynomial Blocklength
- CS-66 Sample Compression Conjecture (Linear Size in VC Dimension)
- CS-76 Computability of the Shannon Capacity of Finite Graphs
- CS-81 Li-Li Undirected Multiple-Unicast Network Coding Conjecture
- CS-82 Capacity Region of General 3-Receiver Discrete Memoryless Broadcast Channels
- CS-100 10 Lectures and 42 Open Problems — Deterministic Restricted Isometry Property matrices
- CS-103 10 Lectures and 42 Open Problems — Gilbert-Varshamov bound
- CS-104 10 Lectures and 42 Open Problems — The Deletion Channel
- CS-127 Hellinger contraction with biased Boolean outputs
- CS-128 Sharp binary-channel information contraction on the cube
- CS-136 Quasipolynomial trace samples for arbitrary symbols
- CS-168 Uniform quasipolynomial worst-case trace reconstruction
- CS-176 Superpolynomial worst-case trace sample lower bounds
- CS-227 Finite-field least squares as statistical decoding
- CS-245 Exact rank-one decoding and a factorized no-QRAM quantum baseline
- CS-246 Hidden Goppa presentations versus public-code decoding
- CS-247 Certificates for hidden Goppa structure and bounded decoding
- CS-273 Asymptotic Goodness of Function-Field-Tower Codes
- CS-291 Half-Distance Decoding for Hypergraph Codes
- CS-292 Multiplicity Decoding for Order-Domain Codes
- CS-295 Optimal Rates of Collusion-Secure Fingerprinting Codes
- CS-334 Randomized Communication Complexity of Distributed Triangle Detection
- CS-336 Simultaneously Adaptive Universal Source Coding
- CS-343 Average-Case Hardness of Quasi-Cyclic Code Problems
- CS-365 Theta Invariants and New Families of MRD Codes
- CS-366 Explicit RIP Matrices Beyond Square-Root Sparsity
- CS-367 Square-Root Sparsity for Explicit RIP Matrices
- CS-391 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- CS-398 Local-to-Global Tensorization of Information Functionals
- CS-399 Capacity Criteria for Arbitrarily Varying Channels with Causal State Information
- CS-400 Decidability of Linear Information Inequalities
- CS-401 Tight Bounds for Many-User Multiple-Access Coding
- CS-403 Capacity and Reliability of Mismatched Decoding
- CS-436 Information-Theoretic Additive Randomized Encodings
- CS-441 Near-Linear List Decoding of AEL and Ta-Shma Codes
- CS-457 10 Lectures and 42 Open Problems — Certifying the Restricted Isometry Property
- CS-473 When frequency selectivity can and cannot improve multi-user capacity
- CS-474 What is actually exponential in single-carrier equalization?
- CS-505 Rank-profile compression for finite-field time-series models
- CS-639 Hardness of Decoding Random Linear Codes
- CS-654 Universal Semantic Communication Across Different Meanings
- CS-655 Fast Instance-Optimal Decoders for Compressed Sensing
- CS-664 Explicit Deterministic Restricted Isometry Matrices
- CS-717 Sequential Decoding of Nonbinary Convolutional Codes
- CS-718 Convolutional Codes for Retrieval, Sensing, and Rank Metrics