Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs

DOI10.4230/LIPICS.ITCS.2019.32MaRDI QIDQ5090407zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, A. 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

zbMATH Keywords

bootstrap percolationentropygossip spreadinglocally correctable codesmatroidspanoidsunion-closed family

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Spanning configurations and representation stability
• Transitive-closure spanners: a survey
• scientific article; zbMATH DE number 1107620
• Spanners of Hypercube-Derived Networks
• Spanning structures and universality in sparse hypergraphs
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• Structured Co-spans: An Algebra of Interaction Protocols
• scientific article; zbMATH DE number 1408421
• Spanning trees on graphs and lattices inddimensions

Cites work

• 3-query locally decodable codes of subexponential length
• A resolution of the Sylvester-Gallai problem of J.-P. Serre
• Breaking the quadratic barrier for 3-LCC's over the reals
• Dense locally testable codes cannot have constant rate and distance
• Expander graphs and their applications
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Families of finite sets in which no set is covered by the union of \(r\) others
• Fractional Sylvester–Gallai theorems
• scientific article; zbMATH DE number 842012 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• Incidence theorems and their applications
• Locally decodable codes
• Lower bounds for 2-query LCCs over large alphabet
• Lower bounds for graph bootstrap percolation via properties of polynomials
• Maximum union-free subfamilies
• On r-cover-free families
• On coset leader graphs of structured linear codes
• On the efficiency of local decoding procedures for error-correcting codes
• Pseudorandom Generators in Propositional Proof Complexity
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Short proofs are narrow—resolution made simple
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• The journey of the union-closed sets conjecture
• Towards 3-query locally decodable codes of subexponential length
• Union-closed families of sets

This page was built for publication: Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090407)