Pages that link to "Item:Q1872732"
From MaRDI portal
The following pages link to In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732):
Displaying 50 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- Pseudorandom generators for combinatorial checkerboards (Q395607) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Avoiding simplicity is complex (Q693072) (← links)
- Complexity theory. Abstracts from the workshop held November 11--17, 2018 (Q782965) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- A zero-one law for RP and derandomization of AM if NP is not small (Q2389331) (← links)
- Robust simulations and significant separations (Q2407096) (← links)
- Upward separations and weaker hypotheses in resource-bounded measure (Q2465636) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- Natural proofs versus derandomization (Q2805512) (← links)
- Sublinear root detection and new hardness results for sparse polynomials over finite fields (Q2816831) (← links)
- Input-oblivious proof systems and a uniform complexity perspective on P/poly (Q2828212) (← links)
- Massive online teaching to bounded learners (Q2986853) (← links)
- Learning mixtures of spherical gaussians (Q2986854) (← links)
- Low-weight halfspaces for sparse boolean vectors (Q2986855) (← links)
- Learnability of DNF with representation-specific queries (Q2986856) (← links)
- Can theories be tested? (Q2986857) (← links)
- Making evolution rigorous (Q2986858) (← links)
- On the convergence of the Hegselmann-Krause system (Q2986859) (← links)
- Is privacy compatible with truthfulness? (Q2986860) (← links)
- Differentially private data analysis of social networks via restricted sensitivity (Q2986861) (← links)
- Characterizing the sample complexity of private learners (Q2986862) (← links)
- Barriers in cryptography with weak, correlated and leaky sources (Q2986863) (← links)
- On the possibilities and limitations of pseudodeterministic algorithms (Q2986864) (← links)
- Evasiveness through a circuit lens (Q2986865) (← links)
- The garden-hose model (Q2986866) (← links)
- Space-bounded communication complexity (Q2986867) (← links)
- Towards an optimal query efficient PCP? (Q2986868) (← links)
- A characterization of approximation resistance for even k-partite CSPs (Q2986869) (← links)
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction (Q2986870) (← links)
- On the power of many one-bit provers (Q2986871) (← links)
- Approaching utopia (Q2986872) (← links)
- Learning and incentives in user-generated content (Q2986873) (← links)
- Welfare maximization and the supermodular degree (Q2986874) (← links)
- Reachability in graph timelines (Q2986875) (← links)
- Runtime guarantees for regression problems (Q2986877) (← links)
- An energy complexity model for algorithms (Q2986878) (← links)
- Streaming computations with a loquacious prover (Q2986880) (← links)
- Adversary lower bound for the k-sum problem (Q2986881) (← links)
- Stronger methods of making quantum interactive proofs perfectly complete (Q2986882) (← links)
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time (Q2986885) (← links)
