The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\) (Q2087770) (← links)
- The complexity of finding fair independent sets in cycles (Q2087771) (← links)
- Improved hitting set for orbit of ROABPs (Q2087774) (← links)
- On hitting-set generators for polynomials that vanish rarely (Q2099672) (← links)
- Quantum versus randomized communication complexity, with efficient players (Q2099674) (← links)
- The complexity of approximating the complex-valued Potts model (Q2125077) (← links)
- Amplification with one \textsf{NP} oracle query (Q2125078) (← links)
- Expander-based cryptography meets natural proofs (Q2125080) (← links)
- Computing zero-dimensional tropical varieties via projections (Q2149946) (← links)
- A quasi-linear irreducibility test in \(\mathbb{K}[[x]][y]\) (Q2149947) (← links)
- Improved bounds on the an-complexity of \(O(1)\)-linear functions (Q2159467) (← links)
- Quadratic lower bounds for algebraic branching programs and formulas (Q2159469) (← links)
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond (Q2159471) (← links)
- A cost-scaling algorithm for computing the degree of determinants (Q2159472) (← links)
- Zeros and approximations of holant polynomials on the complex plane (Q2169310) (← links)
- Communication complexity with small advantage (Q2182866) (← links)
- On \(\epsilon\)-sensitive monotone computations (Q2198153) (← links)
- 2-local random reductions to 3-valued functions (Q2269002) (← links)
- Hardness amplification via space-efficient direct products (Q2269003) (← links)
- Balancing syntactically multilinear arithmetic circuits (Q2269004) (← links)
- Probabilistic communication complexity over the reals (Q2269005) (← links)
- Dimension characterizations of complexity classes (Q2269007) (← links)
- Depth-4 lower bounds, determinantal complexity: a unified approach (Q2281250) (← links)
- On the relationship between statistical zero-knowledge and statistical randomized encodings (Q2281251) (← links)
- Simulation theorems via pseudo-random properties (Q2281252) (← links)
- On derandomized composition of Boolean functions (Q2281253) (← links)
- Hierarchy theorems for testing properties in size-oblivious query complexity (Q2281254) (← links)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (Q2281256) (← links)
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs (Q2304167) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- Random resolution refutations (Q2311546) (← links)
- Vanishing of Littlewood-Richardson polynomials is in P (Q2311547) (← links)
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials (Q2311548) (← links)
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights (Q2323358) (← links)
- A quadratic lower bound for homogeneous algebraic branching programs (Q2323359) (← links)
- Interactive proofs and a Shamir-like result for real number computations (Q2323360) (← links)
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees (Q2323361) (← links)
- Special issue: Conference on computational complexity 2014. Guest editor's foreword (Q2351387) (← links)
- A parallel repetition theorem for entangled projection games (Q2351389) (← links)
- Quantum algorithms for learning symmetric juntas via the adversary bound (Q2351390) (← links)
- Equivalence of polynomial identity testing and polynomial factorization (Q2351391) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- Monomials in arithmetic circuits: complete problems in the counting hierarchy (Q2353185) (← links)
- Complexity of tropical and MIN-plus linear prevarieties (Q2353186) (← links)
- Lower bounds for testing triangle-freeness in Boolean functions (Q2353187) (← links)
- The remote set problem on lattices (Q2353188) (← links)
- Rank-one quantum games (Q2353189) (← links)
- Computing Frobenius maps and factoring polynomials (Q2366168) (← links)
- Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\) (Q2366169) (← links)
