| 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 | 2024-08-21 | Paper |
| Cut sparsification of the Clique beyond the Ramanujan bound: a separation of cut versus spectral sparsification | 2024-07-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6190881 | 2024-02-06 | Paper |
| Improved non-approximability results for vertex cover with density constraints | 2024-01-29 | Paper |
| Minimum vertex cover, distributed decision-making, and communication complexity | 2024-01-05 | Paper |
| Structure in approximation classes | 2023-12-12 | Paper |
| Expansion and flooding in dynamic random networks with node churn | 2023-10-12 | Paper |
| Percolation and epidemic processes in one-dimensional small-world networks (extended abstract) | 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 |
| https://portal.mardi4nfdi.de/entity/Q5077145 | 2022-05-18 | Paper |
| Approximating satisfiable satisfiability problems (extended abstract) | 2021-12-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5009564 | 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 | 2021-07-23 | Paper |
| A New Algorithm for the Robust Semi-random Independent Set Problem | 2021-02-02 | Paper |
| Finding a Bounded-Degree Expander Inside a Dense One | 2021-02-02 | Paper |
| From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More | 2020-08-18 | Paper |
| Find Your Place: Simple Distributed Algorithms for Community Detection | 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 | 2019-10-15 | Paper |
| Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs | 2019-07-04 | Paper |
| Partitioning into Expanders | 2019-06-20 | Paper |
| Almost Optimal Local Graph Clustering Using Evolving Sets | 2018-08-02 | Paper |
| Approximation of non-boolean 2CSP | 2018-07-16 | Paper |
| Stabilizing Consensus with Many Opinions | 2018-07-16 | Paper |
| An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs | 2018-07-16 | Paper |
| Find Your Place: Simple Distributed Algorithms for Community Detection | 2018-07-16 | Paper |
| Near-Optimal UGC-hardness of Approximating Max k-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 | 2017-12-05 | Paper |
| Simple dynamics for plurality consensus | 2017-09-04 | Paper |
| On the complexity of bisimilarity for value-passing processes | 2017-01-19 | Paper |
| On the one-way function candidate proposed by Goldreich | 2016-10-24 | Paper |
| Pseudorandom generators without the XOR lemma (extended abstract) | 2016-09-29 | Paper |
| Construction of extractors using pseudo-random generators (extended abstract) | 2016-09-29 | Paper |
| On the efficiency of polynomial time approximation schemes | 2016-06-01 | Paper |
| A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs | 2015-08-21 | Paper |
| Multi-way spectral partitioning and higher-order cheeger inequalities | 2015-08-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5500595 | 2015-08-07 | Paper |
| Information spreading in dynamic graphs | 2015-03-25 | Paper |
| Non-approximability results for optimization problems on bounded degree instances | 2015-02-27 | Paper |
| Max cut and the smallest eigenvalue | 2015-02-04 | Paper |
| Information spreading in dynamic graphs | 2014-12-05 | Paper |
| Gowers uniformity, influence of variables, and PCPs | 2014-11-25 | Paper |
| Pseudorandom walks on regular digraphs and the RL vs. L problem | 2014-11-25 | Paper |
| A PCP characterization of NP with optimal amortized query complexity | 2014-09-26 | Paper |
| On the efficiency of local decoding procedures for error-correcting codes | 2014-09-26 | Paper |
| Improved Cheeger's inequality | 2014-08-07 | Paper |
| Multi-way spectral partitioning and higher-order cheeger inequalities | 2014-05-13 | Paper |
| A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs | 2013-10-04 | Paper |
| Max Cut and the Smallest Eigenvalue | 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 | 2012-01-26 | Paper |
| From Logarithmic Advice to Single-Bit Advice | 2011-08-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002794 | 2011-05-24 | Paper |
| Dense Model Theorems and Their Applications | 2011-05-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3078217 | 2011-02-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3059320 | 2010-12-08 | Paper |
| Improved Pseudorandom Generators for Depth 2 Circuits | 2010-09-10 | Paper |
| Time Space Tradeoffs for Attacks against One-Way Functions and PRGs | 2010-08-24 | Paper |
| On uniform amplification of hardness in NP | 2010-08-16 | Paper |
| Hierarchies for semantic classes | 2010-08-16 | Paper |
| A note on minimum-area upward drawing of complete and Fibonacci trees | 2010-05-10 | Paper |
| Gowers Uniformity, Influence of Variables, and PCPs | 2010-03-17 | Paper |
| Pseudorandom Bit Generators That Fool Modular Sums | 2009-10-28 | Paper |
| Extractors Using Hardness Amplification | 2009-10-28 | Paper |
| Theory of Cryptography | 2009-05-14 | Paper |
| Amplifying Collision Resistance: A Complexity-Theoretic Treatment | 2009-03-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549626 | 2009-01-05 | Paper |
| Average-Case Complexity | 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 | 2008-03-11 | Paper |
| Extractors and pseudorandom generators | 2008-02-11 | Paper |
| On Worst‐Case to Average‐Case Reductions for NP Problems | 2007-09-07 | Paper |
| Lower bounds for linear locally decodable codes and private information retrieval | 2007-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3413362 | 2007-01-04 | Paper |
| Pseudorandomness and Combinatorial Constructions | 2006-09-26 | Paper |
| On ε‐biased generators in NC0 | 2006-09-06 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| Compression of samplable sources | 2006-02-08 | Paper |
| Theory of Cryptography | 2005-12-07 | Paper |
| Bounds on the Efficiency of Generic Cryptographic Constructions | 2005-10-28 | Paper |
| Approximating Succinct MaxSat | 2005-10-18 | Paper |
| Approximating the Minimum Spanning Tree Weight in Sublinear Time | 2005-09-16 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 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 | 2005-04-06 | Paper |
| On Local Versus Global Satisfiability | 2005-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650573 | 2005-02-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4470516 | 2004-07-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440423 | 2003-12-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4437488 | 2003-12-02 | Paper |
| Three theorems regarding testing graph properties | 2003-08-06 | Paper |
| Pseudorandom generators without the XOR lemma | 2003-02-04 | Paper |
| On weighted vs unweighted versions of combinatorial optimization problems | 2003-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4780778 | 2002-11-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542548 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535797 | 2002-06-25 | Paper |
| Approximating layout problems on random graphs | 2001-07-18 | Paper |
| The approximability of constraint satisfaction problems | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526966 | 2001-02-28 | Paper |
| Gadgets, Approximation, and Linear Programming | 2000-10-18 | Paper |
| When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree | 2000-10-18 | Paper |
| Interactive and probabilistic proof-checking | 2000-09-04 | Paper |
| A complexity analysis of bisimilarity for value-passing processes | 2000-08-21 | Paper |
| On approximation scheme preserving reducibility and its applications | 2000-06-07 | Paper |
| Max NP-completeness made easy | 2000-01-12 | Paper |
| Improved non-approximability results for minimum vertex cover with density constraints | 2000-01-12 | Paper |
| Structure in Approximation Classes | 1999-10-28 | Paper |
| Weak Random Sources, Hitting Sets, and BPP Simulations | 1999-10-28 | Paper |
| A case study of de-randomization methods for combinatorial approximation algorithms | 1999-07-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4395335 | 1998-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4390865 | 1998-05-26 | Paper |
| On the distributed decision-making complexity of the minimum vertex cover problem | 1997-12-04 | Paper |
