Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (Q2968149): Difference between revisions

Latest revision as of 15:20, 13 November 2024

scientific article; zbMATH DE number 6451591

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Language	Label	Description	Also known as
English	Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes	scientific article; zbMATH DE number 6451591	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Statements

instance of

scholarly article

0 references

title

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (English)

0 references

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes (English)

0 references

0 references

0 references

0 references

0 references

0 references

SIAM Journal on Computing

0 references

Proceedings of the forty-sixth annual ACM symposium on Theory of computing

0 references

publication date

10 March 2017

0 references

26 June 2015

0 references

full work available at URL

https://arxiv.org/abs/1311.7407

0 references

zbMATH Keywords

hardness of approximation

0 references

hypergraph coloring

0 references

short code

0 references

MaRDI profile type

MaRDI publication profile

0 references

describes a project that uses

SuLQ

0 references

cites work

Bounds on the Sample Complexity for Private Learning and Private Data Release

0 references

Characterizing the sample complexity of private learners

0 references

Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

0 references

Q5302085

0 references

Collusion-secure fingerprinting for digital data

0 references

Faster private release of marginals on small databases

0 references

Lower Bounds in Differential Privacy

0 references

Our Data, Ourselves: Privacy Via Distributed Noise Generation

0 references

Theory of Cryptography

0 references

Q3549600

0 references

On the complexity of differentially private data release

0 references

Efficient algorithms for privately releasing marginals via convex relaxations

0 references

Advances in Cryptology – CRYPTO 2004

0 references

New Efficient Attacks on Statistical Disclosure Control Mechanisms

0 references

Privately Releasing Conjunctions and the Statistical Query Barrier

0 references

Iterative Constructions and Private Data Release

0 references

On the geometry of differential privacy

0 references

The price of privately releasing contingency tables and the spectra of random matrices with correlated rows

0 references

The Geometry of Differential Privacy: The Small Database and Approximate Cases

0 references

Differential Privacy and the Fat-Shattering Dimension of Linear Queries

0 references

Interactive privacy via the median mechanism

0 references

Faster Algorithms for Privately Releasing Marginals

0 references

Answering n <sub>{2+o(1)}</sub> counting queries with differential privacy is hard

0 references

New approximation guarantee for chromatic number

0 references

Q3129926

0 references

New hardness results for graph and hypergraph colorings

0 references

Making the Long Code Shorter

0 references

Free Bits, PCPs, and Nonapproximability---Towards Tight Results

0 references

An $\tilde{O}(n^{3/14})$-coloring algorithm for 3-colorable graphs

0 references

Optimal Testing of Reed-Muller Codes

0 references

New approximation algorithms for graph coloring

0 references

Coloring bipartite hypergraphs

0 references

PCPs via the low-degree long code and hardness for constrained hypergraph coloring

0 references

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

0 references

Conditional Hardness for Approximate Coloring

0 references

The hardness of 3-uniform hypergraph coloring

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes

0 references

Hardness of Approximate Hypergraph Coloring

0 references

On the Hardness of 4-Coloring a 3-Colorable Graph

0 references

Optimal Testing of Multivariate Polynomials over Small Prime Fields

0 references

Improved Hardness of Approximating Chromatic Number

0 references

Hardness results for approximate hypergraph coloring

0 references

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

0 references

On the hardness of approximating the chromatic number

0 references

A PRG for lipschitz functions of polynomials with applications to sparsest cut

0 references

Approximate graph coloring by semidefinite programming

0 references

Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs

0 references

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors

0 references

Coloring 3-colorable graphs with o(n 1/5 ) colors

0 references

Q5690468

0 references

A Parallel Repetition Theorem

0 references

Q5500597

0 references

Improving the performance guarantee for approximate graph coloring

0 references

Identifiers

zbMATH Open document ID

0 references

0 references

0 references

10.1145/2591796.2591882

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

conf/stoc/GuruswamiHHSV14

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2968149

@@ Property / cites work @@
+Bounds on the Sample Complexity for Private Learning and Private Data Release
+Normal rank
@@ Property / cites work @@
+Characterizing the sample complexity of private learners
+Normal rank
@@ Property / cites work @@
+Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
+Normal rank
@@ Property / cites work @@
+Q5302085
@@ Property / cites work: Q5302085 / rank @@
+Normal rank
@@ Property / cites work @@
+Collusion-secure fingerprinting for digital data
@@ Property / cites work: Collusion-secure fingerprinting for digital data / rank @@
+Normal rank
@@ Property / cites work @@
+Faster private release of marginals on small databases
+Normal rank
@@ Property / cites work @@
+Lower Bounds in Differential Privacy
@@ Property / cites work: Lower Bounds in Differential Privacy / rank @@
+Normal rank
@@ Property / cites work @@
+Our Data, Ourselves: Privacy Via Distributed Noise Generation
+Normal rank
@@ Property / cites work @@
+Theory of Cryptography
@@ Property / cites work: Theory of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549600
@@ Property / cites work: Q3549600 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of differentially private data release
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for privately releasing marginals via convex relaxations
+Normal rank
@@ Property / cites work @@
+Advances in Cryptology – CRYPTO 2004
@@ Property / cites work: Advances in Cryptology – CRYPTO 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+New Efficient Attacks on Statistical Disclosure Control Mechanisms
+Normal rank
@@ Property / cites work @@
+Privately Releasing Conjunctions and the Statistical Query Barrier
+Normal rank
@@ Property / cites work @@
+Iterative Constructions and Private Data Release
@@ Property / cites work: Iterative Constructions and Private Data Release / rank @@
+Normal rank
@@ Property / cites work @@
+On the geometry of differential privacy
@@ Property / cites work: On the geometry of differential privacy / rank @@
+Normal rank
@@ Property / cites work @@
+The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
+Normal rank
@@ Property / cites work @@
+The Geometry of Differential Privacy: The Small Database and Approximate Cases
+Normal rank
@@ Property / cites work @@
+Differential Privacy and the Fat-Shattering Dimension of Linear Queries
+Normal rank
@@ Property / cites work @@
+Interactive privacy via the median mechanism
@@ Property / cites work: Interactive privacy via the median mechanism / rank @@
+Normal rank
@@ Property / cites work @@
+Faster Algorithms for Privately Releasing Marginals
+Normal rank
@@ Property / cites work @@
+Answering n             <sub>{2+o(1)}</sub>             counting queries with differential privacy is hard
+Normal rank
@@ Property / cites work @@
+New approximation guarantee for chromatic number
@@ Property / cites work: New approximation guarantee for chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Q3129926
@@ Property / cites work: Q3129926 / rank @@
+Normal rank
@@ Property / cites work @@
+New hardness results for graph and hypergraph colorings
+Normal rank
@@ Property / cites work @@
+Making the Long Code Shorter
@@ Property / cites work: Making the Long Code Shorter / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
+Normal rank
@@ Property / cites work @@
+Optimal Testing of Reed-Muller Codes
@@ Property / cites work: Optimal Testing of Reed-Muller Codes / rank @@
+Normal rank
@@ Property / cites work @@
+New approximation algorithms for graph coloring
@@ Property / cites work: New approximation algorithms for graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring bipartite hypergraphs
@@ Property / cites work: Coloring bipartite hypergraphs / rank @@
+Normal rank
@@ Property / cites work @@
+PCPs via the low-degree long code and hardness for constrained hypergraph coloring
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Conditional Hardness for Approximate Coloring
@@ Property / cites work: Conditional Hardness for Approximate Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of 3-uniform hypergraph coloring
@@ Property / cites work: The hardness of 3-uniform hypergraph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
+Normal rank
@@ Property / cites work @@
+Hardness of Approximate Hypergraph Coloring
@@ Property / cites work: Hardness of Approximate Hypergraph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the Hardness of 4-Coloring a 3-Colorable Graph
@@ Property / cites work: On the Hardness of 4-Coloring a 3-Colorable Graph / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Testing of Multivariate Polynomials over Small Prime Fields
+Normal rank
@@ Property / cites work @@
+Improved Hardness of Approximating Chromatic Number
+Normal rank
@@ Property / cites work @@
+Hardness results for approximate hypergraph coloring
+Normal rank
@@ Property / cites work @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating the chromatic number
+Normal rank
@@ Property / cites work @@
+A PRG for lipschitz functions of polynomials with applications to sparsest cut
+Normal rank
@@ Property / cites work @@
+Approximate graph coloring by semidefinite programming
+Normal rank
@@ Property / cites work @@
+Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
+Normal rank
@@ Property / cites work @@
+Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
+Normal rank
@@ Property / cites work @@
+Coloring 3-colorable graphs with o(n 1/5 ) colors
@@ Property / cites work: Coloring 3-colorable graphs with o(n 1/5 ) colors / rank @@
+Normal rank
@@ Property / cites work @@
+Q5690468
@@ Property / cites work: Q5690468 / rank @@
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q5500597
@@ Property / cites work: Q5500597 / rank @@
+Normal rank
@@ Property / cites work @@
+Improving the performance guarantee for approximate graph coloring
+Normal rank
@@ Property / DBLP publication ID @@
+conf/stoc/GuruswamiHHSV14
@@ Property / DBLP publication ID: conf/stoc/GuruswamiHHSV14 / rank @@
+Normal rank