| Publication | Date of Publication | Type |
|---|
| On approximability of satisfiable k -CSPs: I | 2023-12-08 | Paper |
| Optimal inapproximability of satisfiable k-LIN over non-abelian groups | 2023-11-14 | Paper |
| Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$ | 2023-08-12 | Paper |
| On Approximability of Satisfiable k-CSPs: IV | 2023-07-30 | Paper |
| Pseudorandom sets in Grassmann graph have near-perfect expansion | 2023-05-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875460 | 2023-02-03 | Paper |
| Improved Monotonicity Testers via Hypercube Embeddings | 2022-11-16 | Paper |
| UG-hardness to NP-hardness by losing half | 2022-07-27 | Paper |
| Simultaneous max-cut is harder to approximate than max-cut | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5077147 | 2022-05-18 | Paper |
| The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics | 2021-12-14 | Paper |
| On the proof of the 2-to-2 Games Conjecture | 2021-12-09 | Paper |
| An Invariance Principle for the Multi-slice, with Applications | 2021-10-20 | Paper |
| On non-optimally expanding sets in Grassmann graphs | 2021-08-24 | Paper |
| An Improved Dictatorship Test with Perfect Completeness | 2020-11-25 | Paper |
| The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics | 2019-10-15 | Paper |
| Towards a proof of the 2-to-1 games conjecture? | 2019-08-22 | Paper |
| On non-optimally expanding sets in Grassmann graphs | 2019-08-22 | Paper |
| Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs | 2019-06-20 | Paper |
| On Monotonicity Testing and Boolean Isoperimetric-type Theorems | 2018-12-19 | Paper |
| An ~O(n) Queries Adaptive Tester for Unateness | 2018-04-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4607982 | 2018-03-15 | Paper |
| Hardness of Bipartite Expansion. | 2018-03-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5371213 | 2017-10-25 | Paper |
| Candidate hard unique game | 2017-09-29 | Paper |
| On independent sets, 2-to-2 games, and Grassmann graphs | 2017-08-17 | Paper |
| Towards an optimal query efficient PCP? | 2017-05-16 | Paper |
| A characterization of approximation resistance for even k-partite CSPs | 2017-05-16 | Paper |
| A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem | 2017-05-16 | Paper |
| Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors | 2017-03-10 | Paper |
| On Hardness of Approximating the Parameterized Clique Problem | 2016-04-15 | Paper |
| Approximating CSPs Using LP Relaxation | 2015-10-27 | Paper |
| The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 | 2015-08-14 | Paper |
| A characterization of strong approximation resistance | 2015-06-26 | Paper |
| Integrality gaps for sparsest cut and minimum linear arrangement problems | 2014-11-25 | Paper |
| On earthmover distance, metric labeling, and 0-extension | 2014-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191598 | 2014-10-06 | Paper |
| Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing | 2014-09-18 | Paper |
| A Two Prover One Round Game with Strong Soundness | 2014-07-30 | Paper |
| Optimal Long Code Test with One Free Bit | 2014-07-25 | Paper |
| SDP Integrality Gaps with Local ell_1-Embeddability | 2014-07-25 | Paper |
| The Complexity of Somewhat Approximation Resistant Predicates | 2014-07-01 | Paper |
| NP-hardness of approximately solving linear equations over reals | 2014-06-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5417658 | 2014-05-22 | Paper |
| 2 log1-ε n hardness for the closest vector problem with preprocessing | 2014-05-13 | Paper |
| $\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals | 2013-09-25 | Paper |
| Sharp kernel clustering algorithms and their associated Grothendieck inequalities | 2013-05-28 | Paper |
| Hardness of approximating the closest vector problem with pre-processing | 2012-06-26 | Paper |
| Grothendieck-Type Inequalities in Combinatorial Optimization | 2012-06-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3096713 | 2011-11-11 | Paper |
| A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem | 2011-07-06 | Paper |
| Combinatorial theorems about embedding trees on the real line | 2011-06-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002760 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002802 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002828 | 2011-05-24 | Paper |
| On the hardness of learning intersections of two halfspaces | 2011-01-18 | Paper |
| Hardness of Reconstructing Multivariate Polynomials over Finite Fields | 2011-01-17 | Paper |
| Approximate Lasserre Integrality Gap for Unique Games | 2010-09-10 | Paper |
| Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems | 2010-09-07 | Paper |
| SDP Gaps for 2-to-1 and Other Label-Cover Variants | 2010-09-07 | Paper |
| A new multilayered PCP and the hardness of hypergraph vertex cover | 2010-08-16 | Paper |
| Cell-probe lower bounds for the partial match problem | 2010-08-16 | Paper |
| A new PCP outer verifier with applications to homogeneous linear equations and max-bisection | 2010-08-15 | Paper |
| Hardness results for approximate hypergraph coloring | 2010-08-05 | Paper |
| On the power of unique 2-prover 1-round games | 2010-08-05 | Paper |
| Fitting algebraic curves to noisy data | 2010-08-05 | Paper |
| On Earthmover Distance, Metric Labeling, and 0-Extension | 2010-04-29 | Paper |
| On Agnostic Learning of Parities, Monomials, and Halfspaces | 2010-04-29 | Paper |
| Inapproximability Results for Computational Problems on Lattices | 2010-03-05 | Paper |
| Approximate Kernel Clustering | 2010-02-05 | Paper |
| Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies | 2009-08-20 | Paper |
| Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion | 2009-03-12 | Paper |
| Approximation Algorithms for the Max-Min Allocation Problem | 2009-02-17 | Paper |
| Hardness of Embedding Metric Spaces of Equal Size | 2009-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549678 | 2009-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549718 | 2009-01-05 | Paper |
| Hardness of approximating the shortest vector problem in lattices | 2008-12-21 | Paper |
| Inapproximability results for combinatorial auctions with submodular utility functions | 2008-09-12 | Paper |
| Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? | 2008-03-28 | Paper |
| Vertex cover might be hard to approximate to within \(2 - \varepsilon \) | 2008-03-11 | Paper |
| Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique | 2007-09-07 | Paper |
| Improved lower bounds on the randomized complexity of graph properties | 2007-05-11 | Paper |
| Nonembeddability theorems via Fourier analysis | 2006-05-26 | Paper |
| Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms | 2006-04-28 | Paper |
| A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover | 2005-09-16 | Paper |
| Cell-probe lower bounds for the partial match problem | 2004-11-18 | Paper |
| Fitting algebraic curves to noisy data | 2004-11-18 | Paper |
| Parameterized complexity of finding subgraphs with hereditary properties. | 2003-01-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2766822 | 2002-07-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535024 | 2002-06-12 | Paper |
| Evasiveness of Subgraph Containment and Related Properties | 2002-04-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2762499 | 2002-01-09 | Paper |
