The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- Fast exponentiation using the truncation operation (Q2366170) (← links)
- Selection problems via \(m\)-ary queries (Q2366172) (← links)
- On lower bounds for read-\(k\)-times branching programs (Q2366719) (← links)
- Parallel pointer machines (Q2366720) (← links)
- Algorithmic aspects of Suslin's proof of Serre's conjecture (Q2366722) (← links)
- On the efficiency of effective Nullstellensätze (Q2366723) (← links)
- Block-symmetric polynomials correlate with parity better than symmetric (Q2410677) (← links)
- List-decoding Barnes-Wall lattices (Q2410678) (← links)
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace (Q2410679) (← links)
- On the connection between interval size functions and path counting (Q2410681) (← links)
- The minimum oracle circuit size problem (Q2410683) (← links)
- Sunflowers and testing triangle-freeness of functions (Q2410684) (← links)
- Low-degree test with polynomially small error (Q2410685) (← links)
- Dual VP classes (Q2410687) (← links)
- Graph isomorphism, color refinement, and compactness (Q2410688) (← links)
- Topological lower bounds for arithmetic networks (Q2410689) (← links)
- Non-commutative Edmonds' problem and matrix semi-invariants (Q2410690) (← links)
- Approximate nonnegative rank is equivalent to the smooth rectangle bound (Q2422764) (← links)
- Tensor surgery and tensor rank (Q2422765) (← links)
- Asymptotic tensor rank of graph tensors: beyond matrix multiplication (Q2422766) (← links)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) (Q2422767) (← links)
- On the hardness of approximating Multicut and Sparsest-Cut (Q2458939) (← links)
- Computationally private randomizing polynomials and their applications (Q2458940) (← links)
- The quantum adversary method and classical formula size power bounds (Q2458941) (← links)
- Pseudorandomness for approximate counting and sampling (Q2460030) (← links)
- Complexity of ring morphism problems (Q2460031) (← links)
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness (Q2460032) (← links)
- Inductive time-space lower bounds for SAT and related problems (Q2460033) (← links)
- Special issue: Selected papers based on the presentations at the 20th annual IEEE conference on computational complexity, San José, CA, USA, June 11--15, 2005. (Q2464462) (← links)
- The complexity of tensor circuit evaluation (Q2472427) (← links)
- An improved analysis of linear mergers (Q2472428) (← links)
- Communication vs. computation (Q2472429) (← links)
- Polynomial identity testing for depth 3 circuits (Q2472430) (← links)
- A generic time hierarchy with one bit of advice (Q2472432) (← links)
- Every linear threshold function has a low-weight approximator (Q2472433) (← links)
- The complexity of membership problems for circuits over sets of natural numbers (Q2474202) (← links)
- The resolution complexity of independent sets and vertex covers in random graphs (Q2474203) (← links)
- New results on the complexity of the middle bit of multiplication (Q2474204) (← links)
- Pseudorandomness and average-case complexity via uniform reductions (Q2475578) (← links)
- Generalized compact knapsacks, cyclic lattices, and efficient one-way functions (Q2475579) (← links)
- If NP languages are hard on the worst-case, then it is easy to find their hard instances (Q2475580) (← links)
- Special issue: Selected papers from the 19th annual IEEE conference on computational complexity (CCC 2004), Amherst, MA, USA, June 21--24, 2004 (Q2497027) (← links)
- Quantum computation of zeta functions of curves (Q2506162) (← links)
- On the complexity of approximating \(k\)-set packing (Q2506163) (← links)
- Free binary decision diagrams for the computation of \(\text{EAR}_{ n }\) (Q2506164) (← links)
- Circuits on cylinders (Q2506165) (← links)
- A tight lower bound for restricted PIR protocols (Q2506166) (← links)
- On sets of linear forms of maximal complexity (Q2680709) (← links)
- On the hardness of the noncommutative determinant (Q5916037) (← links)
- Derandomizing polynomial identity tests means proving circuit lower bounds (Q5916126) (← links)
