The following pages link to Computational Complexity (Q5900112):
Displaying 50 items.
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits (Q276257) (← links)
- \(\mathrm{SL}_2\) homomorphic hash functions: worst case to average case reduction and short collision search (Q306055) (← links)
- A counterexample to the chain rule for conditional HILL entropy (Q332268) (← links)
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields (Q395606) (← links)
- Computation as an unbounded process (Q418791) (← links)
- Book review of: S. Arora and B. Barak, Computational complexity: a modern approach. (Q465661) (← links)
- Derandomization in game-theoretic probability (Q468727) (← links)
- The complexity of debate checking (Q493647) (← links)
- A polynomial upper bound on Reidemeister moves (Q499087) (← links)
- Hardness of embedding simplicial complexes in \(\mathbb R^d\) (Q621847) (← links)
- Perfect implementation (Q625041) (← links)
- On the complexity of matroid isomorphism problem (Q639843) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- The computational status of physics (Q734210) (← links)
- Mass problems associated with effectively closed sets (Q765664) (← links)
- Computing equilibria: a computational complexity perspective (Q847807) (← links)
- Challenging epistemology: Interactive proofs and zero knowledge (Q959048) (← links)
- Certifying trapdoor permutations, revisited (Q1629429) (← links)
- Matrix rigidity of random Toeplitz matrices (Q1653338) (← links)
- A new asymptotic notation: Weak Theta (Q1666904) (← links)
- Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints (Q1678427) (← links)
- Approximate counting in SMT and value estimation for probabilistic programs (Q1683928) (← links)
- Inventory rationing and markdown strategy in the presence of lead-time sensitive customers (Q1694790) (← links)
- Keeping logic in the trivium of computer science: a teaching perspective (Q1696593) (← links)
- Towards implementation of a generalized architecture for high-level quantum programming language (Q1700813) (← links)
- Limitations of semidefinite programs for separable states and entangled games (Q1731116) (← links)
- Non-interactive proofs of proximity (Q1745962) (← links)
- Matching dependencies: semantics and query answering (Q1762196) (← links)
- Optimal measures and Markov transition kernels (Q1941022) (← links)
- Parameterized random complexity (Q1946497) (← links)
- Parallelization of entanglement-resistant multi-prover interactive proofs (Q2015158) (← links)
- Parameterized counting of partially injective homomorphisms (Q2032353) (← links)
- The efficient certification of knottedness and Thurston norm (Q2037601) (← links)
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP (Q2043015) (← links)
- Efficient adaptively-secure IB-KEMs and VRFs via near-collision resistance (Q2061937) (← links)
- Advice hierarchies among finite automata (Q2084773) (← links)
- Approximate NFA universality motivated by information theory (Q2112188) (← links)
- Lower bounds and hardness magnification for sublinear-time shrinking cellular automata (Q2117099) (← links)
- Expander-based cryptography meets natural proofs (Q2125080) (← links)
- Time- and space-efficient arguments from groups of unknown order (Q2139631) (← links)
- Completeness, approximability and exponential time results for counting problems with easy decision version (Q2143122) (← links)
- Improved bounds on the an-complexity of \(O(1)\)-linear functions (Q2159467) (← links)
- A note on the relation between XOR and selective XOR lemmas (Q2203599) (← links)
- An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems (Q2263220) (← links)
- Fast switch and spline scheme for accurate inversion of nonlinear functions: the new first choice solution to Kepler's equation (Q2284079) (← links)
- \(H\)-colouring \(P_t\)-free graphs in subexponential time (Q2322884) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Complexity analysis of hypergeometric orthogonal polynomials (Q2341332) (← links)
- On the average-case complexity of parameterized clique (Q2344729) (← links)
- ``Selfish'' algorithm for reducing the computational cost of the network survivability analysis (Q2357208) (← links)
