The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- Fourier analysis for probabilistic communication complexity (Q1918947) (← links)
- How can a complex square root be computed in an optimal way? (Q1918948) (← links)
- On the oracle complexity of factoring integers (Q1918949) (← links)
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\) (Q1918950) (← links)
- Weakly complete problems are not rare (Q1918951) (← links)
- Extractors for varieties (Q1926108) (← links)
- On the power of unambiguity in log-space (Q1926109) (← links)
- Inapproximability of the Tutte polynomial of a planar graph (Q1926110) (← links)
- Holographic reduction, interpolation and hardness (Q1926111) (← links)
- Comparing the strength of query types in property testing: the case of \(k\)-colorability (Q1947037) (← links)
- A case of depth-3 identity testing, sparse factorization and duality (Q1947039) (← links)
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems (Q1947040) (← links)
- 2-transitivity is insufficient for local testability (Q1947041) (← links)
- Query-efficient locally decodable codes of subexponential length (Q1947042) (← links)
- Small space analogues of Valiant's classes and the limitations of skew formulas (Q1947043) (← links)
- Complexity of solving tropical linear systems (Q1947044) (← links)
- Special issue: Selected papers based on the presentations at the 27th annual IEEE conference on computational complexity (CCC 2012), Porto, Portugal, June 26--29, 2012 (Q1951178) (← links)
- The complexity of matrix rank and feasible systems of linear equations (Q1961056) (← links)
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm (Q1961057) (← links)
- Randomness complexity of private computation (Q1961058) (← links)
- Adaptive versus nonadaptive queries to NP and P-selective sets (Q1961059) (← links)
- Feasibly continuous type-two functionals (Q1961060) (← links)
- The hardest halfspace (Q1983325) (← links)
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity (Q1983326) (← links)
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs (Q1983330) (← links)
- On the complexity of computing Kronecker coefficients (Q2012174) (← links)
- Sparse affine-invariant linear codes are locally testable (Q2012176) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- The value of help bits in randomized and average-case complexity (Q2012180) (← links)
- Information-theoretic approximations of the nonnegative rank (Q2012181) (← links)
- Multipartite quantum correlation and communication complexities (Q2012182) (← links)
- On the structure of Boolean functions with small spectral norm (Q2012184) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- The robustness of LWPP and WPP, with an application to graph reconstruction (Q2027204) (← links)
- The computational complexity of plethysm coefficients (Q2027205) (← links)
- Linear matroid intersection is in quasi-NC (Q2027206) (← links)
- Smooth and strong PCPs (Q2029773) (← links)
- Resolution with counting: dag-like lower bounds and different moduli (Q2029775) (← links)
- Explicit list-decodable codes with optimal rate for computationally bounded channels (Q2029777) (← links)
- Reversible pebble games and the relation between tree-like and general resolution space (Q2033469) (← links)
- Nullstellensatz size-degree trade-offs from reversible pebbling (Q2040600) (← links)
- Subquadratic-time algorithms for normal bases (Q2040602) (← links)
- Lower bounds for matrix factorization (Q2041242) (← links)
- Blackbox identity testing for sum of special ROABPs and its border class (Q2041244) (← links)
- Nondeterministic and randomized Boolean hierarchies in communication complexity (Q2041245) (← links)
- Lower bounds for arithmetic circuits via the Hankel matrix (Q2051372) (← links)
- Factorization of polynomials given by arithmetic branching programs (Q2051373) (← links)
- Correction to: ``Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs'' (Q2062864) (← links)
- Rank and border rank of Kronecker powers of tensors and Strassen's laser method (Q2062866) (← links)
- A lower bound on determinantal complexity (Q2087768) (← links)
