| Publication | Date of Publication | Type |
|---|
| Interactions of computational complexity theory and mathematics | 2024-03-20 | Paper |
| Good permutation codes based on the shuffle-exchange network | 2023-10-23 | Paper |
| Connections between graphs and matrix spaces | 2023-10-12 | Paper |
| On the power and limitations of branch and cut | 2023-07-12 | Paper |
| Robustly self-ordered graphs: constructions and applications to property testing | 2023-07-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6115395 | 2023-07-12 | Paper |
| On linear-algebraic notions of expansion | 2022-12-26 | Paper |
| Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification | 2022-09-14 | Paper |
| On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions | 2022-08-30 | Paper |
| The complexity of graph connectivity | 2022-08-18 | Paper |
| An Optimal "It Ain't Over Till It's Over" Theorem | 2022-08-06 | Paper |
| Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5028363 | 2022-02-09 | Paper |
| Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) | 2021-12-01 | Paper |
| The uncertainty principle: Variations on a theme | 2021-03-17 | Paper |
| Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization | 2020-07-08 | Paper |
| Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs | 2020-05-28 | Paper |
| Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings | 2019-10-02 | Paper |
| Prediction from partial information and hindsight, with application to circuit lower bounds | 2019-07-10 | Paper |
| More barriers for rank methods, via a "numeric to symbolic" transfer | 2019-04-08 | Paper |
| Mathematics and Computation | 2018-11-09 | Paper |
| Explicit Capacity Approaching Coding for Interactive Communication | 2018-09-19 | Paper |
| Local expanders | 2018-08-03 | Paper |
| Towards Optimal Deterministic Coding for Interactive Communication | 2018-07-16 | Paper |
| Efficient algorithms for tensor scaling, quantum marginals and moment polytopes | 2018-04-12 | Paper |
| Teaching and Compressing for Low VC-Dimension | 2018-02-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601849 | 2018-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4591373 | 2017-11-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368747 | 2017-10-10 | Paper |
| Proof Complexity Lower Bounds from Algebraic Circuit Complexity | 2017-10-10 | Paper |
| Non-commutative arithmetic circuits with division | 2017-05-19 | Paper |
| Reed–Muller Codes for Random Erasures and Errors | 2017-04-28 | Paper |
| Symmetric LDPC codes and local testing | 2017-03-31 | Paper |
| Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation | 2017-03-10 | Paper |
| Restriction access | 2016-10-07 | Paper |
| Short proofs are narrow—resolution made simple | 2016-09-29 | Paper |
| Pseudorandomness for network algorithms | 2016-09-01 | Paper |
| Tiny families of functions with random properties (preliminary version) | 2016-09-01 | Paper |
| On the power of finite automata with both nondeterministic and probabilistic states (preliminary version) | 2016-09-01 | Paper |
| Quantum Computing Since Democritus, A Book Review | 2016-06-15 | Paper |
| Smooth Boolean Functions are Easy | 2016-04-15 | Paper |
| Population recovery and partial identification | 2016-03-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3467518 | 2016-02-02 | Paper |
| Algebrization | 2015-09-24 | Paper |
| Sum-of-squares Lower Bounds for Planted Clique | 2015-08-21 | Paper |
| Reed-Muller Codes for Random Erasures and Errors | 2015-08-21 | Paper |
| On derandomizing algorithms that err extremely rarely | 2015-06-26 | Paper |
| Toward better formula lower bounds | 2015-06-26 | Paper |
| Breaking the quadratic barrier for 3-LCC's over the reals | 2015-06-26 | Paper |
| Expanders that beat the eigenvalue bound | 2015-05-07 | Paper |
| Characterizing non-deterministic circuit size | 2015-05-07 | Paper |
| New direct-product testers and 2-query PCPs | 2015-02-04 | Paper |
| 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction | 2014-11-25 | Paper |
| RANDOMNESS — A COMPUTATIONAL COMPLEXITY PERSPECTIVE | 2014-11-11 | Paper |
| Extractors and pseudo-random generators with optimal seed length | 2014-09-26 | Paper |
| Space complexity in propositional calculus | 2014-09-26 | Paper |
| SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY | 2014-09-01 | Paper |
| IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM | 2014-09-01 | Paper |
| Public-key cryptography from different assumptions | 2014-08-13 | Paper |
| Non-commutative circuits and the sum-of-squares problem | 2014-08-13 | Paper |
| Interactive proofs of proximity | 2014-08-07 | Paper |
| Fractional Sylvester–Gallai theorems | 2014-07-25 | Paper |
| Linear Systems over Composite Moduli | 2014-07-25 | Paper |
| Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes | 2014-06-05 | Paper |
| Partial Derivatives in Arithmetic Complexity and Beyond | 2014-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2856504 | 2013-10-29 | Paper |
| Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique | 2013-07-29 | Paper |
| New Direct-Product Testers and 2-Query PCPs | 2013-03-19 | Paper |
| An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas | 2013-03-07 | Paper |
| 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction | 2013-01-03 | Paper |
| Randomness extractors - applications and constructions | 2012-10-24 | Paper |
| Kakeya Sets, New Mergers, and Old Extractors | 2011-10-18 | Paper |
| On the Circuit Complexity of Perfect Hashing | 2011-08-19 | Paper |
| Simplified Derandomization of BPP Using a Hitting Set Generator | 2011-08-19 | Paper |
| On Yao’s XOR-Lemma | 2011-08-19 | Paper |
| Non-commutative circuits and the sum-of-squares problem | 2011-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002767 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002788 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002792 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002796 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002825 | 2011-05-24 | Paper |
| One-way multiparty communication lower bound for pointer jumping with applications | 2011-04-26 | Paper |
| Extractors and rank extractors for polynomial sources | 2011-02-18 | Paper |
| Symmetric LDPC Codes and Local Testing | 2010-10-12 | Paper |
| Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized | 2010-09-06 | Paper |
| Extractors | 2010-08-16 | Paper |
| Randomness-efficient low degree tests and short PCPs via epsilon-biased sets | 2010-08-16 | Paper |
| Simulating independence | 2010-08-16 | Paper |
| Derandomizing homomorphism testing in general groups | 2010-08-15 | Paper |
| A new family of Cayley expanders (?) | 2010-08-15 | Paper |
| Depth through breadth, or why should we attend talks in other areas? | 2010-08-15 | Paper |
| Randomness conductors and constant-degree lossless expanders | 2010-08-05 | Paper |
| Expanders from symmetric codes | 2010-08-05 | Paper |
| Simulating independence | 2010-07-14 | Paper |
| Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques | 2010-05-26 | Paper |
| Towards a Study of Low-Complexity Graphs | 2009-07-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5302082 | 2009-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5302098 | 2009-01-05 | Paper |
| Neighborly embedded manifolds | 2008-12-02 | Paper |
| Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals | 2008-11-27 | Paper |
| The Power and Weakness of Randomness in Computation | 2008-09-18 | Paper |
| Pairwise Independence and Derandomization | 2008-09-01 | Paper |
| Expander graphs and their applications | 2008-07-21 | Paper |
| Randomness – A Computational Complexity Perspective | 2008-06-05 | Paper |
| An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs | 2008-05-05 | Paper |
| A strong direct product theorem for corruption and the multiparty communication complexity of disjointness | 2007-11-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5421717 | 2007-10-24 | Paper |
| Extracting Randomness Using Few Independent Sources | 2007-09-07 | Paper |
| Derandomizing Homomorphism Testing in General Groups | 2007-09-07 | Paper |
| Robust Local Testability of Tensor Products of LDPC Codes | 2007-08-28 | Paper |
| Reducing the seed length in the Nisan-Wigderson generator | 2007-05-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3413301 | 2007-01-04 | Paper |
| Extracting Randomness via Repeated Condensing | 2006-06-01 | Paper |
| Expanders in group algebras | 2006-01-26 | Paper |
| Near optimal seperation of tree-like and general resolution | 2005-07-05 | Paper |
| Pseudorandom Generators in Propositional Proof Complexity | 2005-02-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650567 | 2005-02-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4826684 | 2004-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542521 | 2004-01-27 | Paper |
| The Quantum Communication Complexity of Sampling | 2004-01-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440431 | 2003-12-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440439 | 2003-12-17 | Paper |
| Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus | 2003-12-14 | Paper |
| On interactive proofs with a laconic prover | 2003-11-17 | Paper |
| Short proofs are narrow—resolution made simple | 2003-06-25 | Paper |
| In search of an easy witness: Exponential time vs. probabilistic polynomial time. | 2003-05-14 | Paper |
| Simple analysis of graph tests for linearity and PCP | 2003-04-03 | Paper |
| Entropy waves, the zig-zag graph product, and new constant-degree expanders | 2002-10-13 | Paper |
| Space Complexity in Propositional Calculus | 2002-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542587 | 2002-09-17 | Paper |
| Randomness vs time: Derandomization under a uniform assumption | 2002-07-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535028 | 2002-06-12 | Paper |
| Depth-3 arithmetic circuits over fields of characteristic zero | 2002-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234056 | 2001-08-27 | Paper |
| A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents | 2001-06-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527043 | 2001-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526985 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526986 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527004 | 2001-02-28 | Paper |
| Superpolynomial lower bounds for monotone span programs | 2000-05-14 | Paper |
| Expanders that beat the eigenvalue bound: Explicit construction and applications | 1999-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4231906 | 1999-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230353 | 1999-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228516 | 1999-07-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230323 | 1999-04-22 | Paper |
| Techniques for bounding the convergence rate of genetic algorithms | 1999-03-30 | Paper |
| On data structures and asymmetric communication complexity | 1999-01-06 | Paper |
| Tiny families of functions with random properties: A quality-size trade-off for hashing | 1998-07-19 | Paper |
| Lower bounds on arithmetic circuits via partial derivatives | 1998-06-11 | Paper |
| On the Power of Finite Automata with both Nondeterministic and Probabilistic States | 1998-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4343445 | 1997-07-06 | Paper |
| The Tree Model for Hashing: Lower and Upper Bounds | 1997-03-25 | Paper |
| A method for obtaining randomized algorithms with small tail probabilities | 1997-03-03 | Paper |
| Super-logarithmic depth lower bounds via the direct sum in communication complexity | 1996-11-10 | Paper |
| Boolean complexity classes vs. their arithmetic analogs | 1996-10-07 | Paper |
| On rank vs. communication complexity | 1996-09-15 | Paper |
| Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy | 1996-07-02 | Paper |
| Search Problems in the Decision Tree Model | 1995-08-06 | Paper |
| Derandomized graph products | 1995-07-16 | Paper |
| On the second eigenvalue of hypergraphs | 1995-05-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234123 | 1995-01-01 | Paper |
| Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems | 1994-11-24 | Paper |
| Constructing Small Sets that are Uniform in Arithmetic Progressions | 1994-11-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4284631 | 1994-11-13 | Paper |
| Hardness vs randomness | 1994-11-06 | Paper |
| Non-deterministic communication complexity with few witnesses | 1994-11-06 | Paper |
| Monotone circuits for matching require linear depth | 1994-08-21 | Paper |
| \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs | 1994-05-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4287360 | 1994-04-12 | Paper |
| Combinatorial characterization of read-once formulae | 1993-10-24 | Paper |
| Randomized vs. deterministic decision tree complexity for read-once Boolean functions | 1993-10-10 | Paper |
| Universal traversal sequences for expander graphs | 1993-08-08 | Paper |
| \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom | 1993-06-29 | Paper |
| On read-once threshold formulae and their randomized decision tree complexity | 1993-05-16 | Paper |
| Rounds in Communication Complexity Revisited | 1993-05-16 | Paper |
| Geometric medians | 1993-01-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4011254 | 1992-09-27 | Paper |
| Linear-size constant-depth polylog-threshold circuits | 1992-06-27 | Paper |
| A lower bound on the area of permutation layouts | 1991-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3212276 | 1990-01-01 | Paper |
| Monotone Circuits for Connectivity Require Super-Logarithmic Depth | 1990-01-01 | Paper |
| Toward Understanding Exclusive Read | 1990-01-01 | Paper |
| Linear Circuits over $\operatorname{GF}(2)$ | 1990-01-01 | Paper |
| On computations with integer division | 1989-01-01 | Paper |
| Simulations among concurrent-write PRAMs | 1988-01-01 | Paper |
| The complexity of parallel search | 1988-01-01 | Paper |
| A tradeoff between search and update time for the implicit dictionary problem | 1988-01-01 | Paper |
| Rubber bands, convex embeddings and graph connectivity | 1988-01-01 | Paper |
| The Discrete Logarithm Hides $O(\log n)$ Bits | 1988-01-01 | Paper |
| Relations between Concurrent-Write Models of Parallel Computation | 1988-01-01 | Paper |
| The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$ | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3804186 | 1988-01-01 | Paper |
| How to share memory in a distributed system | 1987-01-01 | Paper |
| A Time-Space Tradeoff for Element Distinctness | 1987-01-01 | Paper |
| The Complexity of Parallel Sorting | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3777937 | 1987-01-01 | Paper |
| Constructing a perfect matching is in random NC | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3725558 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3745272 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4725777 | 1986-01-01 | Paper |
| Rectilinear Graphs and Their Embeddings | 1985-01-01 | Paper |
| Trade-Offs between Depth and Width in Parallel Computation | 1985-01-01 | Paper |
| A fast parallel algorithm for the maximal independent set problem | 1985-01-01 | Paper |
| Succinct representations of graphs | 1983-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3325624 | 1983-01-01 | Paper |
| Improving the performance guarantee for approximate graph coloring | 1983-01-01 | Paper |
