Constructing Ramsey graphs from Boolean function representations

DOI10.1007/S00493-014-2367-1zbMath1349.05230OpenAlexW1996712932MaRDI QIDQ397068

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

Ramsey graphsOR function

Mathematics Subject Classification ID

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

Related Items (8)

An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ Unnamed Item ⋮ On the modulo degree complexity of Boolean functions ⋮ Explicit two-source extractors and resilient functions ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Cites Work

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

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