| Publication | Date of Publication | Type |
|---|
On the Gaussian surface area of spectrahedra
| 2024-09-20 | Paper |
A reverse Minkowski theorem
Annals of Mathematics. Second Series | 2024-01-02 | Paper |
Bounds on the density of smooth lattice coverings
| 2023-11-08 | Paper |
An integer parallelotope with small surface area
Journal of Functional Analysis | 2023-09-20 | Paper |
A simple proof of a reverse Minkowski theorem for integral lattices
| 2023-06-06 | Paper |
Polynomial data structure lower bounds in the group model
SIAM Journal on Computing | 2022-04-01 | Paper |
A Tight Reverse Minkowski Inequality for the Epstein Zeta Function
| 2022-01-13 | Paper |
On the Gaussian surface area of spectrahedra
| 2021-12-02 | Paper |
New bounds on the density of lattice coverings
Journal of the American Mathematical Society | 2021-11-04 | Paper |
The minrank of random graphs
| 2021-07-28 | Paper |
Concentration of Markov chains with bounded moments
Annales de l'Institut Henri Poincaré. Probabilités et Statistiques | 2021-02-15 | Paper |
Bounds on Dimension Reduction in the Nuclear Norm
Lecture Notes in Mathematics | 2020-08-21 | Paper |
The list-decoding size of Fourier-sparse Boolean functions
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
On the lattice isomorphism problem
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Concentration of Markov chains with bounded moments
| 2019-06-17 | Paper |
A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space
Discrete Analysis | 2019-01-09 | Paper |
Kneser graphs are like Swiss cheese
Discrete Analysis | 2019-01-09 | Paper |
The Minrank of Random Graphs
IEEE Transactions on Information Theory | 2018-12-04 | Paper |
The restricted isometry property of subsampled Fourier matrices
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Efficient quantum algorithms for (gapped) group testing and junta testing
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
The list-decoding size of Fourier-sparse Boolean functions
| 2018-01-24 | Paper |
Tight hardness of the non-commutative Grothendieck problem
Theory of Computing | 2018-01-10 | Paper |
Counterexamples to a conjecture of Woods
Duke Mathematical Journal | 2017-10-24 | Paper |
Long monotone paths in line arrangements
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
A reverse Minkowski theorem
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Pseudorandomness of ring-LWE for any ring and modulus
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
The restricted isometry property of subsampled Fourier matrices
Lecture Notes in Mathematics | 2017-07-13 | Paper |
An Inequality for Gaussians on Lattices
SIAM Journal on Discrete Mathematics | 2017-05-24 | Paper |
A Sharp Tail Bound for the Expander Random Sampler
| 2017-03-29 | Paper |
Quantum XOR games
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Minimizing the flow time without migration
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
A Note on Koldobsky's Lattice Slicing Inequality
| 2016-08-17 | Paper |
A note on discrete Gaussian combinations of lattice vectors
Chicago Journal of Theoretical Computer Science | 2016-08-16 | Paper |
Recovering short generators of principal ideals in cyclotomic rings
Advances in Cryptology – EUROCRYPT 2016 | 2016-07-15 | Paper |
Towards Strong Reverse Minkowski-type Inequalities for Lattices
| 2016-06-22 | Paper |
A counterexample to monotonicity of relative mass in random walks
Electronic Communications in Probability | 2016-05-23 | Paper |
On the space complexity of linear programming with preprocessing
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
On lattices, learning with errors, random linear codes, and cryptography
Journal of the ACM | 2015-11-11 | Paper |
Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Lattice problems and norm embeddings
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Conditional hardness for approximate coloring
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Bounded-error quantum state identification and exponential separations in communication complexity
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Krivine schemes are optimal
Proceedings of the American Mathematical Society | 2014-11-19 | Paper |
Near-optimal and explicit Bell inequality violations
Theory of Computing | 2014-10-06 | Paper |
Efficient Rounding for the Noncommutative Grothendieck Inequality
Theory of Computing | 2014-10-06 | Paper |
Classical hardness of learning with errors
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Efficient rounding for the noncommutative Grothendieck inequality
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Elementary proofs of Grothendieck theorems for completely bounded norms
Journal of Operator Theory | 2014-07-14 | Paper |
An optimal lower bound on the communication complexity of gap-Hamming-distance
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Quantum one-way communication can be exponentially stronger than classical communication
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
On the Lattice Isomorphism Problem
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Simultaneous communication protocols with quantum and classical messages
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
On ideal lattices and learning with errors over rings
Journal of the ACM | 2014-02-17 | Paper |
Entropy-based bounds on dimension reduction in \(L^1\)
Israel Journal of Mathematics | 2013-10-31 | Paper |
The Euclidean distortion of flat tori
Journal of Topology and Analysis | 2013-06-27 | Paper |
A toolkit for ring-LWE cryptography
Advances in cryptology -- EUROCRYPT 2013. 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26--30, 2013. Proceedings | 2013-05-31 | Paper |
An optimal lower bound on the communication complexity of gap-Hamming-distance
SIAM Journal on Computing | 2013-02-04 | Paper |
Locally decodable codes and the failure of cotype for projective tensor products
Electronic Research Announcements in Mathematical Sciences | 2012-12-03 | Paper |
scientific article; zbMATH DE number 6096706 (Why is no real title available?)
| 2012-10-21 | Paper |
Tensor-based hardness of the shortest vector problem to within almost polynomial factors
Theory of Computing | 2012-09-27 | Paper |
Upper bounds on the noise threshold for fault-tolerant quantum computing
| 2011-10-05 | Paper |
On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
Theory of Computing | 2011-05-24 | Paper |
Unique games with entangled provers are easy
SIAM Journal on Computing | 2011-04-04 | Paper |
An optimal randomized cell probe lower bound for approximate nearest neighbor searching
SIAM Journal on Computing | 2010-11-04 | Paper |
Learning with errors over rings. (Abstract)
Lecture Notes in Computer Science | 2010-09-29 | Paper |
Better Gap-Hamming Lower Bounds via Better Round Elimination
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
The Euclidean Distortion of Flat Tori
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Simulating quantum correlations with finite communication
SIAM Journal on Computing | 2010-09-06 | Paper |
On lattices, learning with errors, random linear codes, and cryptography
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
A new multilayered {PCP} and the hardness of hypergraph vertex cover
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
New lattice based cryptographic constructions
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Conditional Hardness for Approximate Coloring
SIAM Journal on Computing | 2010-07-07 | Paper |
On ideal lattices and learning with errors over rings
Advances in Cryptology – EUROCRYPT 2010 | 2010-06-01 | Paper |
Lattice enumeration using extreme pruning
Advances in Cryptology – EUROCRYPT 2010 | 2010-06-01 | Paper |
Bounded-error quantum state identification and exponential separations in communication complexity
SIAM Journal on Computing | 2010-03-17 | Paper |
On the complexity of lattice problems with polynomial approximation factors
The LLL Algorithm | 2010-03-05 | Paper |
Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures
Journal of Cryptology | 2009-05-08 | Paper |
A note on the distribution of the distance from a lattice
Discrete & Computational Geometry | 2009-03-24 | Paper |
Lattice-based Cryptography
Post-Quantum Cryptography | 2009-03-12 | Paper |
scientific article; zbMATH DE number 5485482 (Why is no real title available?)
| 2009-01-05 | Paper |
Lattice problems in NP ∩ coNP
Journal of the ACM | 2008-12-21 | Paper |
Improved Inapproximability of Lattice and Coding Problems With Preprocessing
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Adiabatic quantum computation is equivalent to standard quantum computation
SIAM Review | 2008-12-16 | Paper |
scientific article; zbMATH DE number 5320237 (Why is no real title available?)
| 2008-09-03 | Paper |
Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing
Automata, Languages and Programming | 2008-08-28 | Paper |
Impossibility of a Quantum Speed-Up with a Faulty Oracle
Automata, Languages and Programming | 2008-08-28 | Paper |
Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1-Complete
Automata, Languages and Programming | 2008-08-28 | Paper |
Independent sets in graph powers are almost contained in juntas
Geometric and Functional Analysis. GAFA | 2008-05-14 | Paper |
Adiabatic quantum computation is equivalent to standard quantum computation
SIAM Journal on Computing | 2008-03-28 | Paper |
Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
SIAM Journal on Computing | 2008-03-28 | Paper |
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Journal of Computer and System Sciences | 2008-03-11 | Paper |
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Israel Journal of Mathematics | 2008-02-22 | Paper |
New lattice-based cryptographic constructions
Journal of the ACM | 2008-01-14 | Paper |
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
Advances in Cryptology - EUROCRYPT 2006 | 2007-09-24 | Paper |
Lattice-Based Cryptography
Lecture Notes in Computer Science | 2007-09-04 | Paper |
The hardness of 3-uniform hypergraph coloring
Combinatorica | 2007-01-02 | Paper |
Combinatorial algorithms for the unsplittable flow problem
Algorithmica | 2006-06-14 | Paper |
The Complexity of the Local Hamiltonian Problem
SIAM Journal on Computing | 2006-06-01 | Paper |
The complexity of the covering radius problem
Computational Complexity | 2006-02-07 | Paper |
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
SIAM Journal on Computing | 2005-09-16 | Paper |
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2005-08-12 | Paper |
Quantum Computation and Lattice Problems
SIAM Journal on Computing | 2005-02-21 | Paper |
Long monotone paths in line arrangements
Discrete & Computational Geometry | 2005-02-11 | Paper |
scientific article; zbMATH DE number 2119652 (Why is no real title available?)
| 2004-11-29 | Paper |
Temporary tasks assignment resolved
Algorithmica | 2003-08-17 | Paper |
Priority algorithms for makespan minimization in the subset model.
Information Processing Letters | 2003-01-21 | Paper |
On-line restricted assignment of temporary tasks with unknown durations.
Information Processing Letters | 2003-01-21 | Paper |
Off-line temporary tasks assignment.
Theoretical Computer Science | 2003-01-21 | Paper |
Minimizing the Flow Time Without Migration
SIAM Journal on Computing | 2002-09-29 | Paper |
scientific article; zbMATH DE number 1757944 (Why is no real title available?)
| 2002-06-20 | Paper |
Maximizing job benefits on-line
Journal of Scheduling | 2002-05-14 | Paper |
On-line bin-stretching
Theoretical Computer Science | 2002-03-03 | Paper |
scientific article; zbMATH DE number 1670528 (Why is no real title available?)
| 2001-11-11 | Paper |
