Publication:2968149

DOI10.1137/140995520zbMath1359.68104DBLPconf/stoc/GuruswamiHHSV14arXiv1311.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

zbMATH Keywords

hardness of approximationhypergraph coloringshort code

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

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

• SuLQ

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

This page was built for publication: Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes