scientific article; zbMATH DE number 1559537
From MaRDI portal
Publication:4526985
Recommendations
- On circuit lower bounds from derandomization
- scientific article; zbMATH DE number 7758304
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Three XOR-lemmas -- an exposition
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- 2-Xor revisited: satisfiability and probabilities of functions
- Hardness hypotheses, derandomization, and circuit complexity
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Tighter connections between derandomization and circuit lower bounds
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
Cited in
(only showing first 100 items - show all)- Arthur and Merlin as oracles
- Mining circuit lower bound proofs for meta-algorithms
- Random oracles and non-uniformity
- Hardness vs randomness
- Pseudorandom generators without the XOR lemma
- A broader view on the limitations of information processing and communication by nature
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Can every randomized algorithm be derandomized?
- The parameterized complexity of maximality and minimality problems
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Welfare maximization and the supermodular degree
- Hardness amplification within NP against deterministic algorithms
- Approximation of boolean functions by combinatorial rectangles
- Pseudorandomness when the odds are against you
- Differentially private data analysis of social networks via restricted sensitivity
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of nonuniformity in proofs of security
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Metric structures and probabilistic computation
- A new general derandomization method
- Query complexity in errorless hardness amplification
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Fourier concentration from shrinkage
- Chernoff-type direct product theorems
- Pseudorandom generators for combinatorial checkerboards
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Space-bounded communication complexity
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Approaching utopia, strong truthfulness and externality-resistant mechanisms
- Low-depth witnesses are easy to find
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Derandomized parallel repetition theorems for free games
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- Learnability of DNF with representation-specific queries
- Hardness amplification within NP
- Improved hardness amplification in NP
- Streaming computations with a loquacious prover
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Improved direct product theorems for randomized query complexity
- Infeasibility of instance compression and succinct PCPs for NP
- On generic complexity of the problem of representation of natural numbers by sum of two squares
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Competing provers protocols for circuit evaluation
- Investigations concerning the structure of complete sets
- Avoiding simplicity is complex
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- The complexity of explicit constructions
- On pseudorandomness and resource-bounded measure
- Small-bias is not enough to hit read-once CNF
- The garden-hose model
- Pseudorandom generators without the XOR lemma (extended abstract)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Easiness assumptions and hardness tests: Trading time for zero error
- Randomness buys depth for approximate counting
- Complexity of hard-core set proofs
- Pseudo-random generators for all hardnesses
- On Yao's XOR-lemma
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- On the convergence of the Hegselmann-Krause system
- Lower bounds for non-black-box zero knowledge
- Robust optimization in the presence of uncertainty
- Adversary lower bound for the \(k\)-sum problem
- Uniformly hard languages.
- scientific article; zbMATH DE number 1833418 (Why is no real title available?)
- The size of SPP
- Randomness vs time: Derandomization under a uniform assumption
- Relations between average-case and worst-case complexity
- Evaluating matrix circuits
- An energy complexity model for algorithms
- Derandomization from Algebraic Hardness
- ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
- Simplified derandomization of BPP using a hitting set generator
- On derandomized composition of Boolean functions
- scientific article; zbMATH DE number 7561738 (Why is no real title available?)
- scientific article; zbMATH DE number 7561753 (Why is no real title available?)
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- An equational approach to secure multi-party computation
- Almost \(k\)-wise independence and hard Boolean functions.
- Evasiveness through a circuit lens (extended abstract)
- Runtime guarantees for regression problems
- Quantified Derandomization: How to Find Water in the Ocean
- The generic complexity of the bounded problem of graphs clustering
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Properties and applications of Boolean function composition
- A note on perfect correctness by derandomization
- Resource-based corruptions and the combinatorics of hidden diversity
- Parallel identity testing for skew circuits with big powers and applications
- Reachability in graph timelines
- Simple and efficient batch verification techniques for verifiable delay functions
- Time hierarchies for sampling distributions
- On generic complexity of the discrete logarithm problem
- The journey from NP to TFNP hardness
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- Is privacy compatible with truthfulness?
- Amplification and Derandomization without Slowdown
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4526985)
