| Publication | Date of Publication | Type |
|---|
| Sum-of-squares lower bounds for the minimum circuit size problem | 2024-11-19 | Paper |
| Perfect matching in random graphs is as hard as Tseitin | 2024-07-19 | Paper |
Perfect matching in random graphs is as hard as Tseitin
TheoretiCS | 2024-06-27 | Paper |
| scientific article; zbMATH DE number 7788365 (Why is no real title available?) | 2024-01-15 | Paper |
On the impossibility of key agreements from quantum random oracles
Advances in Cryptology – CRYPTO 2022 | 2023-06-28 | Paper |
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
(available as arXiv preprint) | 2023-02-03 | Paper |
scientific article; zbMATH DE number 7563818 (Why is no real title available?)
Theory of Computing | 2022-07-26 | Paper |
Tensor network complexity of multilinear maps
(available as arXiv preprint) | 2022-07-18 | Paper |
Improved Inapproximability of Rainbow Coloring
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Simplified inpproximability of hypergraph coloring via t-agreeing families | 2019-04-01 | Paper |
Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
IEEE Transactions on Information Theory | 2018-06-27 | Paper |
Dense subset sum may be the hardest
(available as arXiv preprint) | 2018-01-24 | Paper |
On the impossibility of cryptography with tamperable randomness
Algorithmica | 2018-01-05 | Paper |
\((2+\varepsilon)\)-Sat is NP-hard
SIAM Journal on Computing | 2017-10-06 | Paper |
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
A characterization of approximation resistance for even \(k\)-partite CSPs
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
On the power of many one-bit provers
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
| Subset sum in the absence of concentration | 2017-01-24 | Paper |
On the usefulness of predicates
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
On the NP-hardness of approximating ordering-constraint satisfaction problems
Theory of Computing | 2015-08-21 | Paper |
Randomly supported independence and resistance
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Inapproximability of NP-complete variants of Nash equilibrium
Theory of Computing | 2014-10-06 | Paper |
On the impossibility of cryptography with tamperable randomness
Advances in Cryptology – CRYPTO 2014 | 2014-08-07 | Paper |
Inapproximability of treewidth and related problems
Journal of Artificial Intelligence Research | 2014-04-09 | Paper |
| On quadratic threshold CSPs | 2014-03-25 | Paper |
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Space-time tradeoffs for subset sum: an improved worst case algorithm
Automata, Languages, and Programming | 2013-08-06 | Paper |
Noise correlation bounds for uniform low degree functions
Arkiv för Matematik | 2013-03-27 | Paper |
Inapproximability of treewidth, one-shot pebbling, and related layout problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Inapproximability of NP-Complete Variants of Nash Equilibrium
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
A simple deterministic reduction for the gap minimum distance of code problem
Automata, Languages and Programming | 2011-07-06 | Paper |
Inapproximability of vertex cover and independent set in bounded degree graphs
Theory of Computing | 2011-05-24 | Paper |
Randomly Supported Independence and Resistance
SIAM Journal on Computing | 2011-05-17 | Paper |
Randomly Supported Independence and Resistance
SIAM Journal on Computing | 2011-05-17 | Paper |
Approximation resistant predicates from pairwise independence
Computational Complexity | 2011-02-18 | Paper |
Towards sharp inapproximability for any 2-CSP
SIAM Journal on Computing | 2011-01-17 | Paper |
Improved inapproximability for submodular maximization
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
On quadratic threshold CSPs
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
| Balanced max 2-sat might not be the hardest | 2009-01-05 | Paper |
Lower Bounds for Subset Cover Based Broadcast Encryption
Progress in Cryptology – AFRICACRYPT 2008 | 2008-06-13 | Paper |
