Pages that link to "Item:Q1872732"

The following pages link to In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732):

Displaying 45 items.

• An equational approach to secure multi-party computation (Q2986886) (← links)
• Publicly verifiable proofs of sequential work (Q2986887) (← links)
• On the power of nonuniformity in proofs of security (Q2986888) (← links)
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems (Q2986889) (← links)
• Resource-based corruptions and the combinatorics of hidden diversity (Q2986890) (← links)
• Time hierarchies for sampling distributions (Q2986891) (← links)
• Properties and applications of boolean function composition (Q2986892) (← links)
• Pseudo-partitions, transversality and locality (Q2986893) (← links)
• Competing provers protocols for circuit evaluation (Q2986894) (← links)
• Catch them if you can (Q2986895) (← links)
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (Q2986896) (← links)
• Robust optimization in the presence of uncertainty (Q2986897) (← links)
• Sorting noisy data with partial information (Q2986898) (← links)
• New affine-invariant codes from lifting (Q2986899) (← links)
• H-wise independence (Q2986900) (← links)
• Sparse extractor families for all the entropy (Q2986901) (← links)
• On the power of conditional samples in distribution testing (Q2986902) (← links)
• NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth (Q3010398) (← links)
• In a World of P=BPP (Q3088186) (← links)
• Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
• Lower bounds on black-box reductions of hitting to density estimation (Q3304157) (← links)
• Local Reductions (Q3448833) (← links)
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size (Q3541802) (← links)
• New algorithms and lower bounds for circuits with linear threshold gates (Q4612481) (← links)
• (Q4638059) (← links)
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (Q4993300) (← links)
• Fine-grained derandomization: from problem-centric to resource-centric complexity (Q5002697) (← links)
• Quantified Derandomization: How to Find Water in the Ocean (Q5060673) (← links)
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization (Q5080481) (← links)
• (Q5091223) (← links)
• Hardness magnification near state-of-the-art lower bounds (Q5091779) (← links)
• Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) (← links)
• Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space (Q5096446) (← links)
• (Q5121895) (← links)
• Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs (Q5130845) (← links)
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk) (Q5363756) (← links)
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES (Q5714674) (← links)
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace (Q5856147) (← links)
• Efficient Construction of Rigid Matrices Using an NP Oracle (Q5863325) (← links)
• Pseudo-random generators for all hardnesses (Q5917585) (← links)
• Easiness assumptions and hardness tests: Trading time for zero error (Q5956013) (← links)
• The power of natural properties as oracles (Q6116834) (← links)
• Rigid matrices from rectangular PCPs (Q6491304) (← links)
• Constructive separations and their consequences (Q6566463) (← links)