Constructing Ramsey graphs from Boolean function representations

DOI10.1007/S00493-014-2367-1MaRDI QIDQ397068zbMATH OpenOpenAlexFDO

Authors Parikshit Gopalan

Publication date 14 August 2014

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-014-2367-1

zbMATH Keywords

OR functionRamsey graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Generalized Ramsey theory (05C55)

Recommendations

• Ramsey graphs cannot be defined by real polynomials
• A Note on Explicit Ramsey Graphs and Modular Sieves
• Ramsey properties of algebraic graphs and hypergraphs
• Improved boolean formulas for the Ramsey graphs
• On efficient constructions of short lists containing mostly Ramsey graphs

Cites work

• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• 3-query locally decodable codes of subexponential length
• A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
• A lower bound on the MOD 6 degree of the OR function
• Constructing Large Set Systems with Given Intersection Sizes Modulo Composite Numbers
• Constructing set systems with prescribed intersection sizes
• scientific article; zbMATH DE number 1332656 (Why is no real title available?)
• scientific article; zbMATH DE number 1088263 (Why is no real title available?)
• Intersection theorems with geometric consequences
• Lower Bounds on Representing Boolean Functions as Polynomials in Z_m
• Query-efficient algorithms for polynomial interpolation over composites
• Representing Boolean functions as polynomials modulo composite numbers
• Set systems with restricted intersections modulo prime powers
• Some remarks on the theory of graphs
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
• The Shannon capacity of a union
• Towards 3-query locally decodable codes of subexponential length

Cited in

(11)

• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Explicit two-source extractors and resilient functions
• A Note on Explicit Ramsey Graphs and Modular Sieves
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• scientific article; zbMATH DE number 7561729 (Why is no real title available?)
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• On the modulo degree complexity of Boolean functions
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• On the degree of Boolean functions as polynomials over \(\mathbb{Z}_m\)
• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: Constructing Ramsey graphs from Boolean function representations

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