DOI10.1145/2775105zbMath1426.05159OpenAlexW2242403914WikidataQ57568009 ScholiaQ57568009MaRDI QIDQ3177749
Boaz Barak, Sanjeev Arora, David Steurer
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2775105
Quantum de Finetti theorems under local measurements with applications,
On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy,
Making the Long Code Shorter,
Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials,
Designing FPT Algorithms for Cut Problems Using Randomized Contractions,
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover,
Domination chain: characterisation, classical complexity, parameterised complexity and approximability,
Approximately counting independent sets in bipartite graphs via graph containers,
Pseudorandom sets in Grassmann graph have near-perfect expansion,
Bi-Covering: Covering Edges with Two Small Subsets of Vertices,
Unnamed Item,
Mathematics of computation through the lens of linear equations and lattices,
Finding and Using Expanders in Locally Sparse Graphs,
Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications,
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy,
Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis,
Spectral algorithms for unique games,
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile,
Approximating Unique Games Using Low Diameter Graph Decomposition,
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut,
Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms,
Improved approximation algorithms for projection games,
Multi-way spectral partitioning and higher-order cheeger inequalities,
Partitioning Well-Clustered Graphs: Spectral Clustering Works!,
The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\),
Unnamed Item,
Computational topology and the Unique Games Conjecture,
Unnamed Item,
Unnamed Item,
Bipartite communities via spectral partitioning,
Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem,
New Tools for Graph Coloring,
Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions,
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs,
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs,
\(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited,
On Khot’s unique games conjecture,
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies,
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1,
Unnamed Item,
Finding Pseudorandom Colorings of Pseudorandom Graphs
