| Publication | Date of Publication | Type |
|---|
New SDP roundings and certifiable approximation for cubic optimization
| 2024-11-28 | Paper |
The minority dynamics and the power of synchronicity
| 2024-11-28 | Paper |
A Ihara-Bass formula for non-Boolean matrices and strong refutations of random CSPs
| 2024-11-19 | Paper |
Bond percolation in small-world graphs with power-law distribution
Theoretical Computer Science | 2024-08-21 | Paper |
Cut sparsification of the Clique beyond the Ramanujan bound: a separation of cut versus spectral sparsification
| 2024-07-19 | Paper |
Computational complexity. A conversation with Bill Gasarch
| 2024-02-06 | Paper |
Improved non-approximability results for vertex cover with density constraints
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Minimum vertex cover, distributed decision-making, and communication complexity
Graph-Theoretic Concepts in Computer Science | 2024-01-05 | Paper |
Structure in approximation classes
Lecture Notes in Computer Science | 2023-12-12 | Paper |
Expansion and flooding in dynamic random networks with node churn
Random Structures & Algorithms | 2023-10-12 | Paper |
Percolation and epidemic processes in one-dimensional small-world networks (extended abstract)
LATIN 2022: Theoretical Informatics | 2023-07-26 | Paper |
Consensus vs Broadcast, with and without Noise
| 2023-02-03 | Paper |
Lower bounds for max-cut via semidefinite programming
| 2022-10-13 | Paper |
Bond Percolation in Small-World Graphs with Power-Law Distribution
| 2022-05-18 | Paper |
Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
Theory of Computing | 2022-05-18 | Paper |
Approximating satisfiable satisfiability problems (extended abstract)
| 2021-12-20 | Paper |
Average whenever you meet: opportunistic protocols for community detection
| 2021-08-04 | Paper |
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
| 2021-08-04 | Paper |
Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
SIAM Journal on Discrete Mathematics | 2021-07-23 | Paper |
A New Algorithm for the Robust Semi-random Independent Set Problem
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Finding a bounded-degree expander inside a dense one
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
SIAM Journal on Computing | 2020-08-18 | Paper |
Find Your Place: Simple Distributed Algorithms for Community Detection
SIAM Journal on Computing | 2020-08-18 | Paper |
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
| 2020-08-12 | Paper |
Optimal lower bounds for sketching graph cuts
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
| 2019-07-04 | Paper |
Partitioning into expanders
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Almost optimal local graph clustering using evolving sets
Journal of the ACM | 2018-08-02 | Paper |
Approximation of non-Boolean 2CSP
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Stabilizing Consensus with Many Opinions
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Find your place: simple distributed algorithms for community detection
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
| 2018-04-19 | Paper |
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
| 2018-03-15 | Paper |
Positive linear programming, parallel approximation and PCP's
Algorithms — ESA '96 | 2017-12-05 | Paper |
Simple dynamics for plurality consensus
Distributed Computing | 2017-09-04 | Paper |
On the complexity of bisimilarity for value-passing processes
Lecture Notes in Computer Science | 2017-01-19 | Paper |
On the one-way function candidate proposed by Goldreich
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Pseudorandom generators without the XOR lemma (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Construction of extractors using pseudo-random generators (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
On the efficiency of polynomial time approximation schemes
Information Processing Letters | 2016-06-01 | Paper |
A new regularity lemma and faster approximation algorithms for low threshold rank graphs
Theory of Computing | 2015-08-21 | Paper |
Multiway spectral partitioning and higher-order Cheeger inequalities
Journal of the ACM | 2015-08-14 | Paper |
Unique games on the hypercube
Chicago Journal of Theoretical Computer Science | 2015-08-07 | Paper |
Information spreading in dynamic graphs
Distributed Computing | 2015-03-25 | Paper |
Non-approximability results for optimization problems on bounded degree instances
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Max CUT and the smallest eigenvalue
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Information spreading in dynamic graphs
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Gowers uniformity, influence of variables, and PCPs
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Pseudorandom walks on regular digraphs and the RL vs. L problem
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
A PCP characterization of NP with optimal amortized query complexity
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
On the efficiency of local decoding procedures for error-correcting codes
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Multi-way spectral partitioning and higher-order Cheeger inequalities
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
A new regularity lemma and faster approximation algorithms for low threshold rank graphs
Lecture Notes in Computer Science | 2013-10-04 | Paper |
Max cut and the smallest eigenvalue
SIAM Journal on Computing | 2013-03-19 | Paper |
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
| 2012-12-11 | Paper |
On Khot’s unique games conjecture
Bulletin of the American Mathematical Society | 2012-01-26 | Paper |
From logarithmic advice to single-bit advice
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Approximation algorithms for unique games
Theory of Computing | 2011-05-24 | Paper |
Dense model theorems and their applications
Theory of Cryptography | 2011-05-19 | Paper |
Pseudorandomness in computer science and in additive combinatorics
| 2011-02-18 | Paper |
Inapproximability of combinatorial optimization problems
| 2010-12-08 | Paper |
Improved pseudorandom generators for depth 2 circuits
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Time space tradeoffs for attacks against one-way functions and PRGs
Advances in Cryptology – CRYPTO 2010 | 2010-08-24 | Paper |
On uniform amplification of hardness in NP
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Hierarchies for semantic classes
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
A note on minimum-area upward drawing of complete and Fibonacci trees
Information Processing Letters | 2010-05-10 | Paper |
Gowers Uniformity, Influence of Variables, and PCPs
SIAM Journal on Computing | 2010-03-17 | Paper |
Pseudorandom Bit Generators That Fool Modular Sums
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Extractors Using Hardness Amplification
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2009-05-14 | Paper |
Amplifying Collision Resistance: A Complexity-Theoretic Treatment
Advances in Cryptology - CRYPTO 2007 | 2009-03-10 | Paper |
scientific article; zbMATH DE number 5485464 (Why is no real title available?)
| 2009-01-05 | Paper |
Average-Case Complexity
Foundations and Trends® in Theoretical Computer Science | 2008-09-01 | Paper |
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
| 2008-06-02 | Paper |
Pseudorandomness and average-case complexity via uniform reductions
Computational Complexity | 2008-03-11 | Paper |
Extractors and pseudorandom generators
Journal of the ACM | 2008-02-11 | Paper |
On Worst‐Case to Average‐Case Reductions for NP Problems
SIAM Journal on Computing | 2007-09-07 | Paper |
Lower bounds for linear locally decodable codes and private information retrieval
Computational Complexity | 2007-01-24 | Paper |
scientific article; zbMATH DE number 5081744 (Why is no real title available?)
| 2007-01-04 | Paper |
Pseudorandomness and Combinatorial Constructions
| 2006-09-26 | Paper |
On ε‐biased generators in NC0
Random Structures & Algorithms | 2006-09-06 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Compression of samplable sources
Computational Complexity | 2006-02-08 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2005-12-07 | Paper |
Bounds on the Efficiency of Generic Cryptographic Constructions
SIAM Journal on Computing | 2005-10-28 | Paper |
Approximating Succinct MaxSat
Journal Of Logic And Computation | 2005-10-18 | Paper |
Approximating the Minimum Spanning Tree Weight in Sublinear Time
SIAM Journal on Computing | 2005-09-16 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Some Applications of Coding Theory in Computational Complexity
| 2005-08-22 | Paper |
The approximability of non-Boolean satisfiability problems and restricted integer programming
Theoretical Computer Science | 2005-04-06 | Paper |
On Local Versus Global Satisfiability
SIAM Journal on Discrete Mathematics | 2005-02-28 | Paper |
scientific article; zbMATH DE number 2134907 (Why is no real title available?)
| 2005-02-18 | Paper |
scientific article; zbMATH DE number 2077131 (Why is no real title available?)
| 2004-07-01 | Paper |
scientific article; zbMATH DE number 2019620 (Why is no real title available?)
| 2003-12-17 | Paper |
scientific article; zbMATH DE number 2011836 (Why is no real title available?)
| 2003-12-02 | Paper |
Three theorems regarding testing graph properties
Random Structures & Algorithms | 2003-08-06 | Paper |
Pseudorandom generators without the XOR lemma
Journal of Computer and System Sciences | 2003-02-04 | Paper |
On weighted vs unweighted versions of combinatorial optimization problems
Information and Computation | 2003-01-14 | Paper |
scientific article; zbMATH DE number 1833397 (Why is no real title available?)
| 2002-11-21 | Paper |
scientific article; zbMATH DE number 1775415 (Why is no real title available?)
| 2002-09-17 | Paper |
scientific article; zbMATH DE number 1756011 (Why is no real title available?)
| 2002-06-25 | Paper |
Approximating layout problems on random graphs
Discrete Mathematics | 2001-07-18 | Paper |
The approximability of constraint satisfaction problems
SIAM Journal on Computing | 2001-03-19 | Paper |
scientific article; zbMATH DE number 1559518 (Why is no real title available?)
| 2001-02-28 | Paper |
Gadgets, Approximation, and Linear Programming
SIAM Journal on Computing | 2000-10-18 | Paper |
When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
SIAM Journal on Computing | 2000-10-18 | Paper |
Interactive and probabilistic proof-checking
Annals of Pure and Applied Logic | 2000-09-04 | Paper |
A complexity analysis of bisimilarity for value-passing processes
Theoretical Computer Science | 2000-08-21 | Paper |
On approximation scheme preserving reducibility and its applications
Theory of Computing Systems | 2000-06-07 | Paper |
Max NP-completeness made easy
Theoretical Computer Science | 2000-01-12 | Paper |
Improved non-approximability results for minimum vertex cover with density constraints
Theoretical Computer Science | 2000-01-12 | Paper |
Structure in Approximation Classes
SIAM Journal on Computing | 1999-10-28 | Paper |
Weak Random Sources, Hitting Sets, and BPP Simulations
SIAM Journal on Computing | 1999-10-28 | Paper |
A case study of de-randomization methods for combinatorial approximation algorithms
Journal of Combinatorial Optimization | 1999-07-27 | Paper |
scientific article; zbMATH DE number 1163722 (Why is no real title available?)
| 1998-08-04 | Paper |
scientific article; zbMATH DE number 1156868 (Why is no real title available?)
| 1998-05-26 | Paper |
On the distributed decision-making complexity of the minimum vertex cover problem
RAIRO - Theoretical Informatics and Applications | 1997-12-04 | Paper |
