Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
From MaRDI portal
Publication:2968149
DOI10.1137/140995520zbMath1359.68104arXiv1311.7407OpenAlexW2591501209WikidataQ56958759 ScholiaQ56958759MaRDI QIDQ2968149
Girish Varma, Srikanth Srinivasan, Prahladh Harsha, Johan T. Håstad, Venkatesan Guruswami
Publication date: 10 March 2017
Published in: SIAM Journal on Computing, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.7407
Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Unnamed Item, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, A Characterization of hard-to-cover CSPs, Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs, Hardness of Rainbow Coloring Hypergraphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- Efficient algorithms for privately releasing marginals via convex relaxations
- The hardness of 3-uniform hypergraph coloring
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Optimal Testing of Multivariate Polynomials over Small Prime Fields
- Faster Algorithms for Privately Releasing Marginals
- Improved Hardness of Approximating Chromatic Number
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- New approximation guarantee for chromatic number
- Coloring 3-colorable graphs with o(n 1/5 ) colors
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Hardness of Approximate Hypergraph Coloring
- A threshold of ln n for approximating set cover
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Making the Long Code Shorter
- Conditional Hardness for Approximate Coloring
- Hardness results for approximate hypergraph coloring
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- New approximation algorithms for graph coloring
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Coloring bipartite hypergraphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Collusion-secure fingerprinting for digital data
- Optimal Testing of Reed-Muller Codes
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- New hardness results for graph and hypergraph colorings
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A PRG for lipschitz functions of polynomials with applications to sparsest cut
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
- On the hardness of approximating the chromatic number
