| Publication | Date of Publication | Type |
|---|
The Kikuchi hierarchy and tensor PCA
Journal of the ACM | 2025-11-27 | Paper |
| The Kikuchi hierarchy and tensor PCA | 2025-08-12 | Paper |
Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
European Journal of Combinatorics | 2024-09-30 | Paper |
| Improved reconstruction of random geometric graphs | 2024-06-24 | Paper |
The Spectrum of the Grigoriev–Laurent Pseudomoments
SIAM Journal on Discrete Mathematics | 2024-01-10 | Paper |
The Role of Directionality, Heterogeneity, and Correlations in Epidemic Risk and Spread
SIAM Review | 2023-05-10 | Paper |
Disordered systems insights on computational hardness
Journal of Statistical Mechanics: Theory and Experiment | 2022-12-13 | Paper |
Disordered Systems Insights on Computational Hardness
(available as arXiv preprint) | 2022-10-15 | Paper |
The planted matching problem: phase transitions and exact results
The Annals of Applied Probability | 2022-02-14 | Paper |
| Trigonometric functions in the $p$-norm | 2021-09-28 | Paper |
| Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier | 2021-07-29 | Paper |
| The Lovász theta function for random regular graphs and community detection in the hard regime | 2021-07-28 | Paper |
| Minimum circuit size, graph isomorphism, and related problems | 2021-06-15 | Paper |
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
A computational approach to animal breeding
Journal of Theoretical Biology | 2020-10-28 | Paper |
| Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs | 2020-08-27 | Paper |
The Lovász theta function for random regular graphs and community detection in the hard regime
SIAM Journal on Computing | 2019-09-02 | Paper |
Rapid mixing for lattice colourings with fewer colours
Journal of Statistical Mechanics: Theory and Experiment | 2019-07-09 | Paper |
| The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness | 2019-07-03 | Paper |
The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
(available as arXiv preprint) | 2019-07-03 | Paper |
Series expansion of the percolation threshold on hypercubic lattices
Journal of Physics A: Mathematical and Theoretical | 2019-03-27 | Paper |
Oriented and degree-generated block models: generating and inferring communities with inhomogeneous degree distributions
Journal of Complex Networks | 2018-10-16 | Paper |
Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
IEEE Transactions on Information Theory | 2018-09-19 | Paper |
Minimum circuit size, graph isomorphism, and related problems
SIAM Journal on Computing | 2018-07-19 | Paper |
| The rigidity transition in random graphs | 2017-09-29 | Paper |
The rigidity transition in random graphs
(available as arXiv preprint) | 2017-09-29 | Paper |
| Designing Strassen's algorithm | 2017-08-30 | Paper |
| Percolation Thresholds in Hyperbolic Lattices | 2017-08-19 | Paper |
Tree codes and a conjecture on exponential sums
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Spectral redemption in clustering sparse networks
Proceedings of the National Academy of Sciences | 2017-02-16 | Paper |
Codes, lower bounds, and phase transitions in the symmetric rendezvous problem
Random Structures & Algorithms | 2017-01-05 | Paper |
| Matrix multiplication algorithms from group orbits | 2016-12-05 | Paper |
The phase transition in random regular exact cover
Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions | 2016-10-21 | Paper |
Computational complexity, phase transitions, and message-passing for community detection
Statistical Physics, Optimization, Inference, and Message-Passing Algorithms | 2016-07-29 | Paper |
| Information-theoretic thresholds for community detection in sparse networks | 2016-07-06 | Paper |
| Information-theoretic thresholds for community detection in sparse networks | 2016-01-11 | Paper |
Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups
SIAM Journal on Discrete Mathematics | 2015-11-27 | Paper |
Group representations that resist random sampling
Random Structures & Algorithms | 2015-11-13 | Paper |
On the bias of traceroute sampling
Journal of the ACM | 2015-11-11 | Paper |
Generic quantum Fourier transforms
ACM Transactions on Algorithms | 2015-09-02 | Paper |
| The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups | 2015-08-03 | Paper |
| Generic quantum Fourier transforms | 2015-08-03 | Paper |
Optimal \(\varepsilon\)-biased sets with just a little randomness
SIAM Journal on Discrete Mathematics | 2015-07-31 | Paper |
| Spatial Mixing for Independent Sets in Poisson Random Trees | 2015-02-21 | Paper |
| Quantum algorithms for Simon's problem over general groups | 2014-12-18 | Paper |
Limitations of quantum coset states for graph isomorphism
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Quantum algorithms for Simon's problem over nonabelian groups
ACM Transactions on Algorithms | 2014-11-18 | Paper |
The complexity of the fermionant and immanants of constant width
Theory of Computing | 2014-10-06 | Paper |
| Heat and Noise on Cubes and Spheres: The Sensitivity of Randomly Rotated Polynomial Threshold Functions | 2014-08-22 | Paper |
An entropic proof of Chang's inequality
SIAM Journal on Discrete Mathematics | 2014-06-19 | Paper |
The phase transition in exact cover
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Small-Bias Sets for Nonabelian Groups
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
The power of choice for random satisfiability
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Tight bounds on the threshold for permuted \(k\)-colorability
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Approximating the permanent via nonabelian determinants
SIAM Journal on Computing | 2012-08-10 | Paper |
A graph integral formulation of the circuit partition polynomial
Combinatorics, Probability and Computing | 2011-12-08 | Paper |
Finding conjugate stabilizer subgroups in PSL(2; q) and related groups
(available as arXiv preprint) | 2011-10-05 | Paper |
| The nature of computation | 2011-09-02 | Paper |
Independent sets in random graphs from the weighted second moment method
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks
Advances in Cryptology – CRYPTO 2011 | 2011-08-12 | Paper |
Limitations of quantum coset states for graph isomorphism
Journal of the ACM | 2011-05-16 | Paper |
On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
SIAM Journal on Computing | 2011-01-17 | Paper |
| Regarding a Representation-Theoretic Conjecture of Wigderson | 2010-09-21 | Paper |
Quasilinear cellular automata
Physica D | 2010-09-11 | Paper |
On the bias of traceroute sampling
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Almost all graphs with average degree 4 are 3-colorable
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
LATIN 2004: Theoretical Informatics
Lecture Notes in Computer Science | 2009-05-07 | Paper |
| Generating hard satisfiable formulas by hiding solutions deceptively | 2009-04-28 | Paper |
| Introduction: where statistical physics meets computation | 2009-02-09 | Paper |
scientific article; zbMATH DE number 5485489 (Why is no real title available?)
(available as arXiv preprint) | 2009-01-05 | Paper |
The Symmetric Group Defies Strong Fourier Sampling
SIAM Journal on Computing | 2008-12-22 | Paper |
| scientific article; zbMATH DE number 5469853 (Why is no real title available?) | 2008-12-21 | Paper |
Principles and Practice of Constraint Programming – CP 2004
Lecture Notes in Computer Science | 2008-09-09 | Paper |
For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets
(available as arXiv preprint) | 2008-09-03 | Paper |
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
SIAM Journal on Computing | 2008-06-19 | Paper |
Counting connected graphs and hypergraphs via the probabilistic method
Random Structures & Algorithms | 2008-01-08 | Paper |
A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
Random Structures & Algorithms | 2008-01-08 | Paper |
Random <i>k</i>‐SAT: Two Moments Suffice to Cross a Sharp Threshold
SIAM Journal on Computing | 2007-06-26 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
MAX <i>k</i>‐CUT and approximating the chromatic number of random graphs
Random Structures & Algorithms | 2006-06-06 | Paper |
On the computational power of probabilistic and quantum branching program
Information and Computation | 2006-01-10 | Paper |
| scientific article; zbMATH DE number 2243408 (Why is no real title available?) | 2006-01-04 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2005-12-16 | Paper |
| New Periodic Orbits for the n-Body Problem | 2005-11-08 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Theory Is Forever
Lecture Notes in Computer Science | 2005-01-18 | Paper |
| scientific article; zbMATH DE number 2119689 (Why is no real title available?) | 2004-11-29 | Paper |
Almost all graphs with average degree 4 are 3-colorable
Journal of Computer and System Sciences | 2004-11-18 | Paper |
| scientific article; zbMATH DE number 2097987 (Why is no real title available?) | 2004-09-07 | Paper |
| scientific article; zbMATH DE number 2086634 (Why is no real title available?) | 2004-08-11 | Paper |
scientific article; zbMATH DE number 2086634 (Why is no real title available?)
(available as arXiv preprint) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2038711 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 2019633 (Why is no real title available?) | 2003-12-17 | Paper |
scientific article; zbMATH DE number 2019633 (Why is no real title available?)
(available as arXiv preprint) | 2003-12-17 | Paper |
| On the 2-colorability of random hypergraphs | 2003-12-17 | Paper |
On the 2-colorability of random hypergraphs
(available as arXiv preprint) | 2003-12-17 | Paper |
| scientific article; zbMATH DE number 1944404 (Why is no real title available?) | 2003-11-10 | Paper |
scientific article; zbMATH DE number 1944404 (Why is no real title available?)
(available as arXiv preprint) | 2003-11-10 | Paper |
| scientific article; zbMATH DE number 1944407 (Why is no real title available?) | 2003-11-10 | Paper |
scientific article; zbMATH DE number 1944407 (Why is no real title available?)
(available as arXiv preprint) | 2003-11-10 | Paper |
| scientific article; zbMATH DE number 1744112 (Why is no real title available?) | 2003-09-18 | Paper |
An analog characterization of the Grzegorczyk hierarchy
Journal of Complexity | 2003-05-14 | Paper |
Ribbon tile invariants from the signed area
Journal of Combinatorial Theory. Series A | 2002-12-11 | Paper |
| scientific article; zbMATH DE number 1834675 (Why is no real title available?) | 2002-11-25 | Paper |
| scientific article; zbMATH DE number 1741011 (Why is no real title available?) | 2002-06-10 | Paper |
Parallel quantum computation and quantum codes
SIAM Journal on Computing | 2002-04-23 | Paper |
Hard tiling problems with simple tiles
Discrete & Computational Geometry | 2002-02-07 | Paper |
| The phase transition in 1-in-\(k\) SAT and NAE 3-SAT | 2002-01-30 | Paper |
Queues, stacks, and transcendentality at the transition to chaos
Physica D | 2002-01-13 | Paper |
| scientific article; zbMATH DE number 1689049 (Why is no real title available?) | 2002-01-09 | Paper |
| scientific article; zbMATH DE number 1583876 (Why is no real title available?) | 2001-04-03 | Paper |
Iteration, inequalities, and differentiability in analog computers
Journal of Complexity | 2001-03-12 | Paper |
Internal diffusion-limited aggregation: parallel algorithms and complexity
Journal of Statistical Physics | 2000-10-08 | Paper |
Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet
Journal of Statistical Physics | 2000-10-08 | Paper |
Braids in classical dynamics
Physical Review Letters | 2000-07-16 | Paper |
Unpredictability and undecidability in dynamical systems
Physical Review Letters | 2000-07-16 | Paper |
Quantum automata and quantum grammars
Theoretical Computer Science | 2000-06-04 | Paper |
Circuits and expressions with nonassociative gates
Journal of Computer and System Sciences | 2000-01-01 | Paper |
The computational complexity of sandpiles
Journal of Statistical Physics | 1999-11-22 | Paper |
Complexity of two-dimensional patterns
Journal of Statistical Physics | 1999-08-08 | Paper |
Majority-vote cellular automata, Ising dynamics, and P-completeness
Journal of Statistical Physics | 1999-05-25 | Paper |
| scientific article; zbMATH DE number 1241089 (Why is no real title available?) | 1999-05-18 | Paper |
Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
Theoretical Computer Science | 1999-01-12 | Paper |
Dynamical recognizers: real-time language recognition by analog computers
Theoretical Computer Science | 1998-08-13 | Paper |
| scientific article; zbMATH DE number 1142937 (Why is no real title available?) | 1998-04-20 | Paper |
Predicting nonlinear cellular automata quickly by decomposing them into linear ones
Physica D | 1997-12-17 | Paper |
| scientific article; zbMATH DE number 1008368 (Why is no real title available?) | 1997-05-12 | Paper |
Recursion theory on the reals and continuous-time computation
Theoretical Computer Science | 1997-02-27 | Paper |
Generalized one-sided shifts and maps of the interval
Nonlinearity | 1992-06-25 | Paper |
Generalized shifts: unpredictability and undecidability in dynamical systems
Nonlinearity | 1991-01-01 | Paper |
Some Polyomino Tilings of the Plane
(available as arXiv preprint) | N/A | Paper |
Tensor cumulants for statistical inference on invariant distributions
(available as arXiv preprint) | N/A | Paper |
