Publication | Date of Publication | Type |
---|
https://portal.mardi4nfdi.de/entity/Q6152159 | 2024-02-12 | Paper |
Reproducibility in learning | 2023-12-08 | Paper |
The power of natural properties as oracles | 2023-08-16 | Paper |
On the power and limitations of branch and cut | 2023-07-12 | Paper |
On the pseudo-deterministic query complexity of NP search problems | 2023-07-12 | Paper |
The fine-grained complexity of multi-dimensional ordering properties | 2022-10-27 | Paper |
https://portal.mardi4nfdi.de/entity/Q5091000 | 2022-07-21 | Paper |
https://portal.mardi4nfdi.de/entity/Q5091223 | 2022-07-21 | Paper |
Agnostic Learning from Tolerant Natural Proofs | 2021-07-28 | Paper |
https://portal.mardi4nfdi.de/entity/Q5002697 | 2021-07-28 | Paper |
https://portal.mardi4nfdi.de/entity/Q4993273 | 2021-06-15 | Paper |
The Surprising Power of Constant Depth Algebraic Proofs | 2021-01-21 | Paper |
https://portal.mardi4nfdi.de/entity/Q5121895 | 2020-09-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q5121900 | 2020-09-22 | Paper |
Does Looking Inside a Circuit Help | 2020-05-26 | Paper |
Pseudorandomness from Shrinkage | 2019-11-21 | Paper |
https://portal.mardi4nfdi.de/entity/Q5743451 | 2019-05-10 | Paper |
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications | 2019-03-28 | Paper |
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications | 2018-07-16 | Paper |
Pseudorandomness when the odds are against you | 2017-10-10 | Paper |
Learning algorithms from natural proofs | 2017-10-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q5351927 | 2017-08-31 | Paper |
Fourier concentration from shrinkage | 2017-07-28 | Paper |
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations | 2017-07-12 | Paper |
Simultaneous Secrecy and Reliability Amplification for a General Channel Model | 2016-12-21 | Paper |
Linear gaps between degrees for the polynomial calculus modulo distinct primes | 2016-09-29 | Paper |
Security-preserving hardness-amplification for any regular one-way function | 2016-09-29 | Paper |
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space | 2016-09-02 | Paper |
Pseudorandomness for network algorithms | 2016-09-01 | Paper |
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility | 2016-04-15 | Paper |
Formula Caching in DPLL | 2015-09-24 | Paper |
https://portal.mardi4nfdi.de/entity/Q5501284 | 2015-08-03 | Paper |
Size-depth trade-offs for threshold circuits | 2015-05-07 | Paper |
New direct-product testers and 2-query PCPs | 2015-02-04 | Paper |
An axiomatic approach to algebrization | 2015-02-04 | Paper |
Can every randomized algorithm be derandomized? | 2014-11-25 | Paper |
Extractors and pseudo-random generators with optimal seed length | 2014-09-26 | Paper |
Designated Verifier Proofs and Their Applications | 2014-08-20 | Paper |
Strong ETH holds for regular resolution | 2014-08-07 | Paper |
An Entropic Proof of Chang's Inequality | 2014-06-19 | Paper |
Time-space tradeoffs in resolution | 2014-05-13 | Paper |
On the (im)possibility of obfuscating programs | 2014-02-17 | Paper |
Finding Heavy Hitters from Lossy or Noisy Data | 2013-10-04 | Paper |
On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} | 2013-05-16 | Paper |
New Direct-Product Testers and 2-Query PCPs | 2013-03-19 | Paper |
Toward a model for backtracking and dynamic programming | 2012-06-26 | Paper |
A stronger model of dynamic programming algorithms | 2011-07-01 | Paper |
Random CNF's are hard for the polynomial calculus | 2011-02-18 | Paper |
On the Exact Complexity of Evaluating Quantified k-CNF | 2010-12-07 | Paper |
Constructive Proofs of Concentration Bounds | 2010-09-10 | Paper |
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized | 2010-09-06 | Paper |
Derandomizing polynomial identity tests means proving circuit lower bounds | 2010-08-16 | Paper |
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification | 2010-04-29 | Paper |
The Complexity of Satisfiability of Small Depth Circuits | 2010-01-14 | Paper |
Models of greedy algorithms for graph problems | 2009-08-27 | Paper |
A zero-one law for RP and derandomization of AM if NP is not small | 2009-07-15 | Paper |
Chernoff-type direct product theorems | 2009-06-30 | Paper |
On the complexity of succinct zero-sum games | 2009-06-17 | Paper |
Chernoff-Type Direct Product Theorems | 2009-03-10 | Paper |
Security Amplification for Interactive Cryptographic Primitives | 2009-03-03 | Paper |
https://portal.mardi4nfdi.de/entity/Q5302082 | 2009-01-05 | Paper |
The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs | 2008-03-11 | Paper |
The resolution complexity of independent sets and vertex covers in random graphs | 2008-03-05 | Paper |
Extracting Randomness Using Few Independent Sources | 2007-09-07 | Paper |
Online Algorithms to Minimize Resource Reallocations and Network Communication | 2007-08-28 | Paper |
Reducing the seed length in the Nisan-Wigderson generator | 2007-05-08 | Paper |
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science | 2006-11-14 | Paper |
Logics for reasoning about cryptographic constructions | 2006-04-28 | Paper |
Near optimal seperation of tree-like and general resolution | 2005-07-05 | Paper |
Derandomizing polynomial identity tests means proving circuit lower bounds | 2005-02-23 | Paper |
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution | 2005-02-21 | Paper |
https://portal.mardi4nfdi.de/entity/Q4737158 | 2004-08-11 | Paper |
Homogenization and the polynomial calculus | 2004-05-27 | Paper |
https://portal.mardi4nfdi.de/entity/Q2768397 | 2003-07-05 | Paper |
In search of an easy witness: Exponential time vs. probabilistic polynomial time. | 2003-05-14 | Paper |
https://portal.mardi4nfdi.de/entity/Q4783716 | 2002-12-08 | Paper |
https://portal.mardi4nfdi.de/entity/Q4780777 | 2002-11-21 | Paper |
https://portal.mardi4nfdi.de/entity/Q4549233 | 2002-08-27 | Paper |
On the complexity of \(k\)-SAT | 2002-08-14 | Paper |
Which problems have strongly exponential complexity? | 2002-07-04 | Paper |
Randomness vs time: Derandomization under a uniform assumption | 2002-07-04 | Paper |
Communication complexity towards lower bounds on circuit depth | 2002-06-17 | Paper |
A Note on Conservativity Relations among Bounded Arithmetic Theories | 2002-05-29 | Paper |
Reducing the complexity of reductions | 2002-05-05 | Paper |
Linear gaps between degrees for the polynomial calculus modulo distinct primes | 2002-03-24 | Paper |
https://portal.mardi4nfdi.de/entity/Q4234077 | 2002-01-30 | Paper |
https://portal.mardi4nfdi.de/entity/Q2754208 | 2001-11-11 | Paper |
https://portal.mardi4nfdi.de/entity/Q4527042 | 2001-03-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q4526985 | 2001-02-28 | Paper |
Improved depth lower bounds for small distance connectivity | 2000-10-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q4952609 | 2000-05-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q4252738 | 2000-04-26 | Paper |
Lower bounds for the polynomial calculus and the Gröbner basis algorithm | 2000-03-30 | Paper |
A Pseudorandom Generator from any One-way Function | 1999-10-28 | Paper |
The relative complexity of NP search problems | 1999-09-13 | Paper |
https://portal.mardi4nfdi.de/entity/Q4258569 | 1999-09-13 | Paper |
https://portal.mardi4nfdi.de/entity/Q4252755 | 1999-08-31 | Paper |
https://portal.mardi4nfdi.de/entity/Q4228483 | 1999-07-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q4250219 | 1999-06-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q4251066 | 1999-06-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q4228469 | 1999-05-18 | Paper |
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting | 1998-06-29 | Paper |
Bounding the Size of Planar Intertwines | 1998-02-09 | Paper |
A tight relationship between generic oracles and type-2 complexity theory | 1997-10-07 | Paper |
Size--Depth Tradeoffs for Threshold Circuits | 1997-05-26 | Paper |
Limits on the power of parallel random access machines with weak forms of write conflict resolution | 1997-03-31 | Paper |
The reachability problem for finite cellular automata | 1997-02-28 | Paper |
Efficient cryptographic schemes provably as secure as subset sum | 1997-01-26 | Paper |
Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs | 1996-12-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q4281540 | 1996-07-29 | Paper |
Exponential lower bounds for the pigeonhole principle | 1993-10-18 | Paper |
On dice and coins: Models of computation for random generation | 1993-08-30 | Paper |
The effect of random restrictions on formula size | 1993-06-29 | Paper |
https://portal.mardi4nfdi.de/entity/Q5750403 | 1990-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q4732126 | 1989-01-01 | Paper |