| nr |
titel |
auteur |
tijdschrift |
jaar |
jaarg. |
afl. |
pagina('s) |
type |
| 1 |
A complexity gap for tree resolution
|
Riis, S.
|
|
2001
|
|
3 |
p. 179-209
|
artikel
|
| 2 |
A counterexample to the chain rule for conditional HILL entropy
|
Krenn, Stephan
|
|
2016
|
|
3 |
p. 567-605
|
artikel
|
| 3 |
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
|
Cai, Jin-Yi
|
|
2019
|
|
3 |
p. 345-408
|
artikel
|
| 4 |
An exponential lower bound on the size of algebraic decision trees for Max
|
Grigoriev, D.
|
|
1998
|
|
3 |
p. 193-203
|
artikel
|
| 5 |
A quadratic lower bound for homogeneous algebraic branching programs
|
Kumar, Mrinal
|
|
2019
|
|
3 |
p. 409-435
|
artikel
|
| 6 |
A quantifier elimination for the theory of p-adic numbers
|
Egidi, L.
|
|
1998
|
|
3 |
p. 205-263
|
artikel
|
| 7 |
A Quantum Characterization Of NP
|
Blier, Hugue
|
|
2011
|
|
3 |
p. 499-510
|
artikel
|
| 8 |
Arthur and Merlin as Oracles
|
Chakaravarthy, Venkatesan T.
|
|
2011
|
|
3 |
p. 505-558
|
artikel
|
| 9 |
Combinatorial PCPs with Efficient Verifiers
|
Meir, Or
|
|
2014
|
|
3 |
p. 355-478
|
artikel
|
| 10 |
Communication complexity towards lower bounds on circuit depth
|
Edmonds, J.
|
|
2001
|
|
3 |
p. 210-246
|
artikel
|
| 11 |
Communication with Contextual Uncertainty
|
Ghazi, Badih
|
|
2017
|
|
3 |
p. 463-509
|
artikel
|
| 12 |
Complexity and Approximability of the Cover Polynomial
|
Bläser, Markus
|
|
2011
|
|
3 |
p. 359-419
|
artikel
|
| 13 |
Composition of semi-LTCs by two-wise tensor products
|
Ben-Sasson, Eli
|
|
2013
|
|
3 |
p. 601-643
|
artikel
|
| 14 |
Compression of Samplable Sources
|
Trevisan, Luca
|
|
2005
|
|
3 |
p. 186-227
|
artikel
|
| 15 |
Correction to: Query-to-Communication Lifting for PNP
|
Göös, Mika
|
|
2019
|
|
3 |
p. 543-544
|
artikel
|
| 16 |
Cryptographic Hardness of Random Local Functions
|
Applebaum, Benny
|
|
2015
|
|
3 |
p. 667-722
|
artikel
|
| 17 |
Derandomized Parallel Repetition Theorems for Free Games
|
Shaltiel, Ronen
|
|
2013
|
|
3 |
p. 565-594
|
artikel
|
| 18 |
Derandomizing Arthur—Merlin games under uniform assumptions
|
Lu, C.-J.
|
|
2001
|
|
3 |
p. 247-259
|
artikel
|
| 19 |
Derandomizing Arthur–Merlin Games using Hitting Sets
|
Miltersen, Peter Bro
|
|
2005
|
|
3 |
p. 256-279
|
artikel
|
| 20 |
Dual VP Classes
|
Allender, Eric
|
|
2016
|
|
3 |
p. 583-625
|
artikel
|
| 21 |
Efficient algorithm for computing the Euler–Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
|
Basu, Saugata
|
|
2006
|
|
3 |
p. 236-251
|
artikel
|
| 22 |
Efficiently Certifying Non-Integer Powers
|
Kaltofen, Erich
|
|
2010
|
|
3 |
p. 355-366
|
artikel
|
| 23 |
Graph Isomorphism, Color Refinement, and Compactness
|
Arvind, V.
|
|
2016
|
|
3 |
p. 627-685
|
artikel
|
| 24 |
Hadamard tensors and lower bounds on multiparty communication complexity
|
Ford, Jeff
|
|
2012
|
|
3 |
p. 595-622
|
artikel
|
| 25 |
Homogeneous Formulas and Symmetric Polynomials
|
Hrubeš, Pavel
|
|
2011
|
|
3 |
p. 559-578
|
artikel
|
| 26 |
Improved Approximation of Linear Threshold Functions
|
Diakonikolas, Ilias
|
|
2012
|
|
3 |
p. 623-677
|
artikel
|
| 27 |
Interactive proofs and a Shamir-like result for real number computations
|
Baartse, Martijn
|
|
2018
|
|
3 |
p. 437-469
|
artikel
|
| 28 |
Interpolation of Shifted-Lacunary Polynomials
|
Giesbrecht, Mark
|
|
2010
|
|
3 |
p. 333-354
|
artikel
|
| 29 |
Language compression and pseudorandom generators
|
Buhrman, Harry
|
|
2005
|
|
3 |
p. 228-255
|
artikel
|
| 30 |
Length 3 Edge-Disjoint Paths Is NP-Hard
|
Alpert, Hannah
|
|
2012
|
|
3 |
p. 511-513
|
artikel
|
| 31 |
Limits on Alternation Trading Proofs for Time–Space Lower Bounds
|
Buss, Samuel R.
|
|
2015
|
|
3 |
p. 533-600
|
artikel
|
| 32 |
Low-degree test with polynomially small error
|
Moshkovitz, Dana
|
|
2016
|
|
3 |
p. 531-582
|
artikel
|
| 33 |
Low-Depth Witnesses are Easy to Find
|
Antunes, Luís
|
|
2011
|
|
3 |
p. 479-497
|
artikel
|
| 34 |
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
|
Lagarde, Guillaume
|
|
2018
|
|
3 |
p. 471-542
|
artikel
|
| 35 |
Lower bounds for linear locally decodable codes and private information retrieval
|
Goldreich, Oded
|
|
2006
|
|
3 |
p. 263-296
|
artikel
|
| 36 |
Lower bounds for modular counting by circuits with modular gates
|
Mix Barrington, D. A.
|
|
1999
|
|
3 |
p. 258-272
|
artikel
|
| 37 |
Lower bounds for the multiplicative complexity of matrix multiplication
|
Bläser, M.
|
|
1999
|
|
3 |
p. 203-226
|
artikel
|
| 38 |
Modular Composition Modulo Triangular Sets and Applications
|
Poteaux, Adrien
|
|
2013
|
|
3 |
p. 463-516
|
artikel
|
| 39 |
New Results on the Complexity of the Middle Bit of Multiplication
|
Wegener, Ingo
|
|
2007
|
|
3 |
p. 298-323
|
artikel
|
| 40 |
Non-commutative Edmonds’ problem and matrix semi-invariants
|
Ivanyos, Gábor
|
|
2016
|
|
3 |
p. 717-763
|
artikel
|
| 41 |
On Approximate Majority and Probabilistic Time
|
Viola, Emanuele
|
|
2009
|
|
3 |
p. 337-375
|
artikel
|
| 42 |
On a Theorem of Razborov
|
Wunderlich, Henning
|
|
2011
|
|
3 |
p. 431-477
|
artikel
|
| 43 |
On reducing factorization to the discrete logarithm problem modulo a composite
|
Pomykała, Jacek
|
|
2012
|
|
3 |
p. 421-429
|
artikel
|
| 44 |
On small space complexity classes of stochastic Turing machines and Arthur-Merlin-games
|
Liskiewicz, M.
|
|
1999
|
|
3 |
p. 273-307
|
artikel
|
| 45 |
On Space and Depth in Resolution
|
Razborov, Alexander
|
|
2017
|
|
3 |
p. 511-559
|
artikel
|
| 46 |
On the Approximation Resistance of a Random Predicate
|
Håstad, Johan
|
|
2009
|
|
3 |
p. 413-434
|
artikel
|
| 47 |
On the Complexity of Succinct Zero-Sum Games
|
Fortnow, Lance
|
|
2008
|
|
3 |
p. 353-376
|
artikel
|
| 48 |
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability
|
Dinur, Irit
|
|
2011
|
|
3 |
p. 413-504
|
artikel
|
| 49 |
Polynomial multiplication over finite fields: from quadratic to straight-line complexity
|
Bshouty, Nader H.
|
|
2006
|
|
3 |
p. 252-262
|
artikel
|
| 50 |
Polynomials that Sign Represent Parity and Descartes’ Rule of Signs
|
Basu, Saugata
|
|
2008
|
|
3 |
p. 377-406
|
artikel
|
| 51 |
Private Approximation of Clustering and Vertex Cover
|
Beimel, Amos
|
|
2009
|
|
3 |
p. 435-494
|
artikel
|
| 52 |
Probabilistic Type-2 Operators and “Almost”-Classes
|
Book, R.V.
|
|
1998
|
|
3 |
p. 265-289
|
artikel
|
| 53 |
Randomness Buys Depth for Approximate Counting
|
Viola, Emanuele
|
|
2013
|
|
3 |
p. 479-508
|
artikel
|
| 54 |
Read-once polynomial identity testing
|
Shpilka, Amir
|
|
2015
|
|
3 |
p. 477-532
|
artikel
|
| 55 |
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
|
Jansen, Maurice
|
|
2013
|
|
3 |
p. 517-564
|
artikel
|
| 56 |
Solvability of systems of polynomial congruences modulo a large prime
|
Huang, M.-D.
|
|
1999
|
|
3 |
p. 227-257
|
artikel
|
| 57 |
Some observations on holographic algorithms
|
Valiant, Leslie G.
|
|
2017
|
|
3 |
p. 351-374
|
artikel
|
| 58 |
Space Hierarchy Results for Randomized and other Semantic Models
|
Kinne, Jeff
|
|
2009
|
|
3 |
p. 423-475
|
artikel
|
| 59 |
Special issue, final part “Conference on Computational Complexity 2004 ” Guest Editor’s foreword
|
Allender, Eric
|
|
2005
|
|
3 |
p. 185
|
artikel
|
| 60 |
Special Issue on the 10th Theory of Cryptography Conference: Editor’s Foreword
|
Goldreich, Oded
|
|
2015
|
|
3 |
p. 563-565
|
artikel
|
| 61 |
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size
|
Moshkovitz, Dana
|
|
2009
|
|
3 |
p. 367-422
|
artikel
|
| 62 |
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers
|
McKenzie, Pierre
|
|
2007
|
|
3 |
p. 211-244
|
artikel
|
| 63 |
The complexity of semilinear problems in succinct representation
|
Bürgisser, Peter
|
|
2006
|
|
3 |
p. 197-235
|
artikel
|
| 64 |
The NOF Multiparty Communication Complexity of Composed Functions
|
Ada, Anil
|
|
2014
|
|
3 |
p. 645-694
|
artikel
|
| 65 |
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
|
Beame, Paul
|
|
2007
|
|
3 |
p. 245-297
|
artikel
|
| 66 |
The Strength of Multilinear Proofs
|
Raz, Ran
|
|
2008
|
|
3 |
p. 407-457
|
artikel
|
| 67 |
Topological lower bounds for arithmetic networks
|
Gabrielov, Andrei
|
|
2016
|
|
3 |
p. 687-715
|
artikel
|
| 68 |
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
|
Dinur, Irit
|
|
2017
|
|
3 |
p. 375-462
|
artikel
|
| 69 |
Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments
|
Pass, Rafael
|
|
2016
|
|
3 |
p. 607-666
|
artikel
|
| 70 |
Upper Bounds for Monotone Planar Circuit Value and Variants
|
Limaye, Nutan
|
|
2009
|
|
3 |
p. 377-412
|
artikel
|
Tijdschrift beschrijving