scientific article; zbMATH DE number 7559092
From MaRDI portal
Publication:5090427
DOI10.4230/LIPIcs.ITCS.2019.49MaRDI QIDQ5090427
Tselil Schramm, Pravesh K. Kothari, Ryan O'Donnell
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1809.01207
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- On the Fourier tails of bounded functions over the discrete cube
- Sum of Squares Lower Bounds from Pairwise Independence
- Randomly Supported Independence and Resistance
- Relations between average case complexity and approximation complexity
- Gadgets, Approximation, and Linear Programming
- SOS Is Not Obviously Automatizable, Even Approximately
- Sum of squares lower bounds for refuting any CSP
- On the Bit Complexity of Sum-of-Squares Proofs
- CSP gaps and reductions in the lasserre hierarchy
- Sum-of-squares meets Nash: lower bounds for finding any equilibrium
- Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
- A new point of NP-hardness for unique games
- Hypercontractivity, sum-of-squares proofs, and their applications
- Some optimal inapproximability results
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Positivstellensatz proofs for the knapsack
This page was built for publication:
