The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- On the security of Goldreich's one-way function (Q430847) (← links)
- Low-depth witnesses are easy to find (Q445240) (← links)
- Complexity and approximability of the cover polynomial (Q445242) (← links)
- On reducing factorization to the discrete logarithm problem modulo a composite (Q445245) (← links)
- On a theorem of Razborov (Q445247) (← links)
- Length 3 edge-disjoint paths is NP-hard (Q445249) (← links)
- A quantum characterization of NP (Q445251) (← links)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma (Q451107) (← links)
- Generic complexity of finitely presented monoids and semigroups (Q451108) (← links)
- Complexity of hard-core set proofs (Q451110) (← links)
- Parameterized proof complexity (Q451111) (← links)
- Interpolation in Valiant's theory (Q451113) (← links)
- Variety evasive sets (Q475333) (← links)
- Using elimination theory to construct rigid matrices (Q475335) (← links)
- Short lists for shortest descriptions in short time (Q475336) (← links)
- Lifting lower bounds for tree-like proofs (Q475337) (← links)
- An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic (Q475340) (← links)
- Combinatorial PCPs with efficient verifiers (Q483706) (← links)
- Randomness buys depth for approximate counting (Q483707) (← links)
- Special issue ``Conference on computational complexity 2013'' -- guest editor's foreword (Q488046) (← links)
- The correct exponent for the Gotsman-Linial conjecture (Q488047) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- Random arithmetic formulas can be reconstructed efficiently (Q488050) (← links)
- How low can approximate degree and quantum query complexity be for total Boolean functions? (Q488052) (← links)
- On the power of non-adaptive learning graphs (Q488054) (← links)
- Read-once polynomial identity testing (Q496300) (← links)
- Limits on alternation trading proofs for time-space lower bounds (Q496301) (← links)
- Composition of semi-LTCs by two-wise tensor products (Q496304) (← links)
- The NOF multiparty communication complexity of composed functions (Q496305) (← links)
- Special issue: Conference on computational complexity (CCC 2010). Selected papers based on the presentations at the 25th annual IEEE conference, Cambridge, MA, USA, June 9--11, 2010 (Q554704) (← links)
- Special issue: Conference on computational complexity (CCC 2009). Selected papers based on the presentations at the 24th annual IEEE computational complexity conference, Paris, France, July 15--18, 2009. (Q619666) (← links)
- Special issue: Selected papers from the 23rd annual IEEE conference on computational complexity (CCC 2008), College Park, MD, USA, June 23--26, 2008. (Q622841) (← links)
- Counting irreducible components of complex algebraic varieties (Q623497) (← links)
- Quadratic lower bound for permanent vs. determinant in any characteristic (Q623498) (← links)
- Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes (Q623500) (← links)
- On the randomness complexity of property testing (Q623502) (← links)
- Communication complexity under product and nonproduct distributions (Q623504) (← links)
- Extractors and rank extractors for polynomial sources (Q626610) (← links)
- On defining integers and proving arithmetic circuit lower bounds (Q626611) (← links)
- Nullstellensätze for zero-dimensional Gröbner bases (Q626612) (← links)
- The black-box query complexity of polynomial summation (Q626615) (← links)
- Robust algorithms for generalized Pham systems (Q626616) (← links)
- Lower bounds and separations for constant depth multilinear circuits (Q626617) (← links)
- Approximation resistant predicates from pairwise independence (Q626619) (← links)
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\) (Q626620) (← links)
- Approximate inclusion-exclusion for arbitrary symmetric functions (Q626621) (← links)
- Using entanglement in quantum multi-prover interactive proofs (Q626625) (← links)
- Disjointness is hard in the multiparty number-on-the-forehead model (Q626627) (← links)
- Private approximation of clustering and vertex cover (Q626661) (← links)
