The following pages link to Computational Complexity (Q172540):
Displaying 50 items.
- The computational complexity of recognizing permutation functions (Q5917358) (← links)
- Every 2-CSP allows nontrivial approximation (Q5919233) (← links)
- Lower bounds for the bilinear complexity of associative algebras (Q5930150) (← links)
- The BNS-Chung criterion for multi-party communication complexity (Q5930151) (← links)
- A compendium of problems complete for symmetric logarithmic space (Q5930152) (← links)
- On the relation between entropy and the average complexity of trajectories in dynamical systems (Q5930153) (← links)
- Small PCPs with low query complexity (Q5946703) (← links)
- Alternation in interaction (Q5946704) (← links)
- A separation of syntactic and nonsyntactic \((1,+k)\)-branching programs (Q5946705) (← links)
- Depth-3 arithmetic circuits over fields of characteristic zero (Q5957088) (← links)
- Which bases admit non-trivial shrinkage of formulae? (Q5957089) (← links)
- Fast computation of the Smith form of a sparse integer matrix (Q5957090) (← links)
- The ''log rank'' conjecture for modular communication complexity (Q5957091) (← links)
- Two oracles that force a big crunch (Q5957723) (← links)
- Reducing the complexity of reductions (Q5957724) (← links)
- Complexity of Positivstellensatz proofs for the knapsack (Q5957725) (← links)
- On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions (Q5957726) (← links)
- A lower bound on the complexity of testing grained distributions (Q6063025) (← links)
- On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing (Q6083214) (← links)
- Parallel algorithms for power circuits and the word problem of the Baumslag group (Q6083216) (← links)
- Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) (Q6113103) (← links)
- Schur polynomials do not have small formulas if the determinant does not (Q6113104) (← links)
- A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory (Q6113105) (← links)
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (Q6113106) (← links)
- The power of natural properties as oracles (Q6116834) (← links)
- A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations (Q6116835) (← links)
- Approximating the chromatic polynomial is as hard as computing it exactly (Q6121107) (← links)
- Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond (Q6172035) (← links)
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares (Q6184293) (← links)
- Improving \(3N\) circuit complexity lower bounds (Q6184294) (← links)
- On Blocky Ranks Of Matrices (Q6489336) (← links)
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\) (Q6542431) (← links)
- KRW composition theorems via lifting (Q6542432) (← links)
- Limits of preprocessing (Q6581870) (← links)
- Streaming approximation resistance of every ordering CSP (Q6581871) (← links)
- Algebraic global gadgetry for surjective constraint satisfaction (Q6581872) (← links)
- The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability (Q6599765) (← links)
- Combinatorial refinement on circulant graphs (Q6599766) (← links)
- Variety evasive subspace families (Q6599767) (← links)
- Determinants vs. algebraic branching programs (Q6624427) (← links)
- Localizability of the approximation method (Q6624428) (← links)
- PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster (Q6655885) (← links)
- Publication:5930150 (← links)
- Publication:5930151 (← links)
- Publication:5930152 (← links)
- Publication:5930153 (← links)
- Publication:5946703 (← links)
- Publication:5946704 (← links)
- Publication:5946705 (← links)
- Publication:5957088 (← links)
