Information and coding theory
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. 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
- Math-112 Capacity of the General Discrete Memoryless Relay Channel
- Math-161 Asymptotic tightness of the binary Gilbert–Varshamov bound
- Math-229 Capacity of the Binary Deletion Channel
- Math-252 Quantum versus Classical Communication Complexity of Total Functions
- Math-254 Reliability Function of the Binary Symmetric Channel Below the Critical Rate
- Math-262 Constant-Query Locally Decodable Codes with Polynomial Blocklength
- Math-297 Sample Compression Conjecture (Linear Size in VC Dimension)
- Math-412 Computability of the Shannon Capacity of Finite Graphs
- Math-451 Li-Li Undirected Multiple-Unicast Network Coding Conjecture
- Math-462 Capacity Region of General 3-Receiver Discrete Memoryless Broadcast Channels
- Math-2068 10 Lectures and 42 Open Problems — Deterministic Restricted Isometry Property matrices
- Math-2071 10 Lectures and 42 Open Problems — Gilbert-Varshamov bound
- Math-2072 10 Lectures and 42 Open Problems — The Deletion Channel
- Math-2969 Hellinger contraction with biased Boolean outputs
- Math-2970 Sharp binary-channel information contraction on the cube
- Math-2978 Quasipolynomial trace samples for arbitrary symbols
- Math-3010 Uniform quasipolynomial worst-case trace reconstruction
- Math-3018 Superpolynomial worst-case trace sample lower bounds
- Math-4416 Finite-field least squares as statistical decoding
- Math-4434 Exact rank-one decoding and a factorized no-QRAM quantum baseline
- Math-4435 Hidden Goppa presentations versus public-code decoding
- Math-4436 Certificates for hidden Goppa structure and bounded decoding
- Math-4462 Asymptotic Goodness of Function-Field-Tower Codes
- Math-4480 Half-Distance Decoding for Hypergraph Codes
- Math-4481 Multiplicity Decoding for Order-Domain Codes
- Math-4484 Optimal Rates of Collusion-Secure Fingerprinting Codes
- Math-4523 Randomized Communication Complexity of Distributed Triangle Detection
- Math-4525 Simultaneously Adaptive Universal Source Coding
- Math-4532 Average-Case Hardness of Quasi-Cyclic Code Problems
- Math-4554 Theta Invariants and New Families of MRD Codes
- Math-4555 Explicit RIP Matrices Beyond Square-Root Sparsity
- Math-4556 Square-Root Sparsity for Explicit RIP Matrices
- Math-4580 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- Math-4587 Local-to-Global Tensorization of Information Functionals
- Math-4588 Capacity Criteria for Arbitrarily Varying Channels with Causal State Information
- Math-4589 Decidability of Linear Information Inequalities
- Math-4590 Tight Bounds for Many-User Multiple-Access Coding
- Math-4592 Capacity and Reliability of Mismatched Decoding
- Math-4625 Information-Theoretic Additive Randomized Encodings
- Math-4630 Near-Linear List Decoding of AEL and Ta-Shma Codes
- Math-4992 10 Lectures and 42 Open Problems — Certifying the Restricted Isometry Property
- Math-5008 When frequency selectivity can and cannot improve multi-user capacity
- Math-5009 What is actually exponential in single-carrier equalization?
- Math-5040 Rank-profile compression for finite-field time-series models
- Math-5174 Hardness of Decoding Random Linear Codes
- Math-5189 Universal Semantic Communication Across Different Meanings
- Math-5190 Fast Instance-Optimal Decoders for Compressed Sensing
- Math-5199 Explicit Deterministic Restricted Isometry Matrices
- Math-5252 Sequential Decoding of Nonbinary Convolutional Codes
- Math-5253 Convolutional Codes for Retrieval, Sensing, and Rank Metrics