Entity usage

This page lists pages that use the given entity (e.g. Q42). The list is sorted by descending page ID, so that newer pages are listed first.

Showing below up to 50 results in range #1 to #50.

PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster: Label: en
Determinants vs. algebraic branching programs: Label: en
Localizability of the approximation method: Label: en
Variety evasive subspace families: Label: en
Combinatorial refinement on circulant graphs: Label: en
The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability: Label: en
Algebraic global gadgetry for surjective constraint satisfaction: Label: en
Streaming approximation resistance of every ordering CSP: Label: en
Limits of preprocessing: Label: en
KRW composition theorems via lifting: Label: en
Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\): Label: en
On Blocky Ranks Of Matrices: Label: en
Improving \(3N\) circuit complexity lower bounds: Label: en
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares: Label: en
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond: Label: en
Approximating the chromatic polynomial is as hard as computing it exactly: Label: en
A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations: Label: en
The power of natural properties as oracles: Label: en
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?: Label: en
A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory: Label: en
Schur polynomials do not have small formulas if the determinant does not: Label: en
Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\): Label: en
Parallel algorithms for power circuits and the word problem of the Baumslag group: Label: en
On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing: Label: en
A lower bound on the complexity of testing grained distributions: Label: en
Communication with contextual uncertainty: Label: en
Relativizing small complexity classes and their theories: Label: en
VPSPACE and a transfer theorem over the reals: Label: en
Sunflowers and testing triangle-freeness of functions: Label: en
On the structure of Boolean functions with small spectral norm: Label: en
On sets of linear forms of maximal complexity: Label: en
A tight lower bound for restricted PIR protocols: Label: en
Circuits on cylinders: Label: en
Free binary decision diagrams for the computation of \(\text{EAR}_{ n }\): Label: en
On the complexity of approximating \(k\)-set packing: Label: en
Quantum computation of zeta functions of curves: Label: en
Special issue: Selected papers from the 19th annual IEEE conference on computational complexity (CCC 2004), Amherst, MA, USA, June 21--24, 2004: Label: en
New results on the complexity of the middle bit of multiplication: Label: en
The resolution complexity of independent sets and vertex covers in random graphs: Label: en
The complexity of membership problems for circuits over sets of natural numbers: Label: en
If NP languages are hard on the worst-case, then it is easy to find their hard instances: Label: en
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions: Label: en
Pseudorandomness and average-case complexity via uniform reductions: Label: en
Every linear threshold function has a low-weight approximator: Label: en
A generic time hierarchy with one bit of advice: Label: en
Polynomial identity testing for depth 3 circuits: Label: en
Communication vs. computation: Label: en
An improved analysis of linear mergers: Label: en
The complexity of tensor circuit evaluation: Label: en
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.: Label: en