| Publication | Date of Publication | Type |
|---|
| Improved monotonicity testers via hypercube embeddings | 2024-09-25 | Paper |
| Almost polynomial factor inapproximability for parameterized \(k\)-clique | 2024-07-05 | Paper |
| On approximability of satisfiable k-CSPs. II | 2024-05-08 | Paper |
| On approximability of satisfiable k-CSPs. III | 2024-05-08 | Paper |
| 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 \(\widetilde O(n)\) queries adaptive tester for unateness | 2018-04-19 | Paper |
| Near-optimal approximation algorithm for simultaneous Max-Cut | 2018-03-15 | Paper |
| Hardness of bipartite expansion | 2018-03-02 | Paper |
| Hardness of approximation | 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 |
| A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem | 2017-05-16 | Paper |
| A characterization of approximation resistance for even \(k\)-partite CSPs | 2017-05-16 | Paper |
| Towards an optimal query efficient PCP? | 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 \(\ell_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 |
| A two-prover one-round game with strong soundness | 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 |
| Sharp kernel clustering algorithms and their associated Grothendieck inequalities | 2014-05-22 | Paper |
| \(2^{\log^{1-\varepsilon} 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 |
| Inapproximability of vertex cover and independent set in bounded degree graphs | 2011-05-24 | Paper |
| SDP gaps and UGC-hardness for max-cut-gain | 2011-05-24 | Paper |
| Query efficient PCPs with perfect completeness | 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 |
| On the power of unique 2-prover 1-round games | 2010-08-05 | Paper |
| Hardness results for approximate hypergraph coloring | 2010-08-05 | Paper |
| Fitting algebraic curves to noisy data | 2010-08-05 | Paper |
| On agnostic learning of parities, monomials, and halfspaces | 2010-04-29 | Paper |
| On earthmover distance, metric labeling, and 0-extension | 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 |
| Hardness of Embedding Metric Spaces of Equal Size | 2009-02-17 | Paper |
| Approximation Algorithms for the Max-Min Allocation Problem | 2009-02-17 | Paper |
| Unique games on expanding constraint graphs are easy (extended abstract) | 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 |
