Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
From MaRDI portal
Publication:5090407
DOI10.4230/LIPIcs.ITCS.2019.32OpenAlexW2892986291MaRDI QIDQ5090407
Yuzhou Gu, Sivakanth Gopi, Zeev Dvir, Avi Wigderson
Publication date: 18 July 2022
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/10125/pdf/LIPIcs-ITCS-2019-32.pdf
entropymatroidbootstrap percolationlocally correctable codesunion-closed familygossip spreadingspanoids
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum union-free subfamilies
- The journey of the union-closed sets conjecture
- 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
- 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
- Pseudorandom Generators in Propositional Proof Complexity
- Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs
- 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
- 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
