The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- On the approximation resistance of a random predicate (Q626662) (← links)
- Upper bounds for monotone planar circuit value and variants (Q626664) (← links)
- On approximate majority and probabilistic time (Q626665) (← links)
- Parallel time and quantifier prefixes (Q626666) (← links)
- Space-efficient counting in graphs on surfaces (Q626667) (← links)
- VPSPACE and a transfer theorem over the reals (Q626668) (← links)
- Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH (Q626670) (← links)
- Constructions of low-degree and error-correcting \(\varepsilon \)-biased generators (Q626671) (← links)
- Lipschitz continuous ordinary differential equations are polynomial-space complete (Q626672) (← links)
- A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\) (Q626674) (← links)
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits (Q626676) (← links)
- The complexity of Boolean functions in different characteristics (Q626677) (← links)
- Are PCPs inherent in efficient arguments? (Q626678) (← links)
- Lower bounds on the randomized communication complexity of read-once functions (Q626679) (← links)
- Space hierarchy results for randomized and other semantic models (Q626680) (← links)
- Sub-constant error probabilistically checkable proof of almost-linear size (Q626681) (← links)
- Interpolation of shifted-lacunary polynomials (Q626682) (← links)
- Efficiently certifying non-integer powers (Q626685) (← links)
- Random CNF's are hard for the polynomial calculus (Q626686) (← links)
- The complexity of the inertia (Q626688) (← links)
- Lower bounds for agnostic learning via approximate rank (Q626689) (← links)
- All natural NP-complete problems have average-case complete versions (Q626691) (← links)
- New results on noncommutative and commutative polynomial identity testing (Q626693) (← links)
- A complexity dichotomy for hypergraph partition functions (Q626694) (← links)
- On matrix rigidity and locally self-correctable codes (Q645122) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Spectral algorithms for unique games (Q645126) (← links)
- The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions (Q645127) (← links)
- Derandomized parallel repetition via structured PCPs (Q645129) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- Homogeneous formulas and symmetric polynomials (Q649096) (← links)
- PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space (Q677988) (← links)
- Lower bounds for monotone span programs (Q677989) (← links)
- Using amplification to compute majority with small majority gates (Q677991) (← links)
- Counting curves and their projections (Q677992) (← links)
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions (Q685705) (← links)
- \(NC^ 1\): The automata-theoretic viewpoint (Q685708) (← links)
- Efficient and optimal exponentiation in finite fields (Q685709) (← links)
- Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\) (Q685711) (← links)
- Existence and efficient construction of fast Fourier transforms on supersolvable groups (Q685713) (← links)
- Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs (Q685715) (← links)
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory (Q685716) (← links)
- On the power of small-depth threshold circuits (Q685717) (← links)
- Some computational problems in linear algebra as hard as matrix multiplication (Q685718) (← links)
- On the rank of certain finite fields (Q685719) (← links)
- Decomposition of algebras over finite fields and number fields (Q685720) (← links)
- Arithmetization: A new method in structural complexity theory (Q685721) (← links)
- On the decidability of sparse univariate polynomial interpolation (Q685722) (← links)
- Towards optimal simulations of formulas by bounded-width programs (Q685723) (← links)
