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)- Chernoff-type direct product theorems
- Hardness vs randomness
- Approximation of boolean functions by combinatorial rectangles
- Almost \(k\)-wise independence and hard Boolean functions.
- Randomness vs time: Derandomization under a uniform assumption
- Random oracles and non-uniformity
- Generic hardness of the Boolean satisfiability problem
- Catalytic space: non-determinism and hierarchy
- Knapsack in graph groups
- Evaluation of circuits over nilpotent and polycyclic groups
- Some results on derandomization
- Tally NP sets and easy census functions.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Uniformly hard languages.
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Fourier concentration from shrinkage
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- A note on perfect correctness by derandomization
- Simple extractors via constructions of cryptographic pseudo-random generators
- On derandomized composition of Boolean functions
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Verification of quantum computation: an overview of existing approaches
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Mining circuit lower bound proofs for meta-algorithms
- On optimal language compression for sets in PSPACE/poly
- Hardness assumptions in the foundations of theoretical computer science
- Reconstructive dispersers and hitting set generators
- Can we locally compute sparse connected subgraphs?
- Zero knowledge and circuit minimization
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Computation of best possible low degree expanders
- The parameterized complexity of maximality and minimality problems
- Lower bounds for non-black-box zero knowledge
- On zero error algorithms having oracle access to one query
- Circuit lower bounds from learning-theoretic approaches
- On derandomizing Yao's weak-to-strong OWF construction
- Simple and efficient batch verification techniques for verifiable delay functions
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- Pseudorandom generators without the XOR lemma (extended abstract)
- Investigations concerning the structure of complete sets
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Computing (and Life) Is All about Tradeoffs
- Book review of: Inevitable randomness in discrete mathematics, by József Beck
- Can every randomized algorithm be derandomized?
- Parallel identity testing for skew circuits with big powers and applications
- Some new consequences of the hypothesis that P has fixed polynomial-size circuits
- Massive online teaching to bounded learners
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Low-weight halfspaces for sparse boolean vectors
- Learnability of DNF with representation-specific queries
- Can theories be tested?
- Making evolution rigorous: the error threshold
- On the convergence of the Hegselmann-Krause system
- Is privacy compatible with truthfulness?
- Differentially private data analysis of social networks via restricted sensitivity
- Characterizing the sample complexity of private learners
- Barriers in cryptography with weak, correlated and leaky sources
- On the possibilities and limitations of pseudodeterministic algorithms
- Evasiveness through a circuit lens (extended abstract)
- The garden-hose model
- Space-bounded communication complexity
- Towards an optimal query efficient PCP?
- A characterization of approximation resistance for even k-partite CSPs
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of many one-bit provers
- Approaching utopia, strong truthfulness and externality-resistant mechanisms
- Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
- Welfare maximization and the supermodular degree
- Reachability in graph timelines
- Runtime guarantees for regression problems
- An energy complexity model for algorithms
- Streaming computations with a loquacious prover
- Adversary lower bound for the k-sum problem
- Stronger methods of making quantum interactive proofs perfectly complete
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- An equational approach to secure multi-party computation
- Publicly verifiable proofs of sequential work
- On the power of nonuniformity in proofs of security
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Resource-based corruptions and the combinatorics of hidden diversity
- Time hierarchies for sampling distributions
- Properties and applications of Boolean function composition
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Competing provers protocols for circuit evaluation
- Catch them if you can
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- Robust optimization in the presence of uncertainty
- Sorting noisy data with partial information
- New affine-invariant codes from lifting
- H-wise independence
- Sparse extractor families for all the entropy
- A PCP characterization of AM
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Simplified derandomization of BPP using a hitting set generator
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- On Yao's XOR-lemma
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)
