Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs
From MaRDI portal
Publication:5112250
DOI10.1137/19M124647XzbMath1443.68115arXiv1809.10372OpenAlexW3025833418MaRDI QIDQ5112250
Avi Wigderson, Sivakanth Gopi, Yuzhou Gu, Zeev Dvir
Publication date: 28 May 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.10372
Combinatorics in computer science (68R05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)
Related Items (2)
Upper bounds on the Boolean rank of Kronecker products ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum union-free subfamilies
- The journey of the union-closed sets conjecture
- Hitting sets when the VC-dimension is small
- Families of finite sets in which no set is covered by the union of \(r\) others
- A resolution of the Sylvester-Gallai problem of J.-P. Serre
- Almost optimal set covers in finite VC-dimension
- On \(r\)-cover-free families
- On coset leader graphs of structured linear codes
- Lower bounds for graph bootstrap percolation via properties of polynomials
- Incidence Theorems and Their Applications
- Dense Locally Testable Codes Cannot Have Constant Rate and Distance
- On the efficiency of local decoding procedures for error-correcting codes
- Expander graphs and their applications
- Towards 3-query locally decodable codes of subexponential length
- Short proofs are narrow—resolution made simple
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- Pseudorandom Generators in Propositional Proof Complexity
- On characterization of entropy function via information inequalities
- Sylvester-Gallai type theorems for quadratic polynomials
- Fractional Sylvester–Gallai theorems
- 3-query locally decodable codes of subexponential length
- Breaking the quadratic barrier for 3-LCC's over the reals
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Tight Lower Bounds for 2-query LCCs over Finite Fields
- Locally Decodable Codes
- Union-closed families of sets
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
This page was built for publication: Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs
