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)- 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
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- On the optimal compression of sets in PSPACE
- Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
- The generic complexity of the graph triangulation problem
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- Sorting noisy data with partial information
- ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
- New affine-invariant codes from lifting
- On the possibilities and limitations of pseudodeterministic algorithms
- On generic complexity of the graph clustering problem with bounded clusters
- On generic complexity of the validity problem for Boolean formulas
- Does looking inside a circuit help?
- Catch them if you can
- scientific article; zbMATH DE number 1789922 (Why is no real title available?)
- Barriers in cryptography with weak, correlated and leaky sources
- \(H\)-wise independence
- Non-convex matrix completion and related problems via strong duality
- Generic hardness of the Boolean satisfiability problem
- Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
- Publicly verifiable proofs of sequential work
- Parallel identity testing for skew circuits with big powers and applications
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- On zero error algorithms having oracle access to one query
- High-rate codes with sublinear-time decoding
- Verification of quantum computation: an overview of existing approaches
- Characterizing the sample complexity of private learners
- Knapsack in graph groups
- Massive online teaching to bounded learners
- A Tight Analysis of Bethe Approximation for Permanent
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Towards hardness of approximation for polynomial time problems
- Simple extractors via constructions of cryptographic pseudo-random generators
- Matrix completion and related problems via strong duality
- Agnostic Learning from Tolerant Natural Proofs
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Zero knowledge and circuit minimization
- Evaluation of circuits over nilpotent and polycyclic groups
- A note on perfect correctness by derandomization
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Some results on derandomization
- Catalytic space: non-determinism and hierarchy
- A PCP characterization of AM
- Tally NP sets and easy census functions.
- scientific article; zbMATH DE number 7559146 (Why is no real title available?)
- (Nondeterministic) hardness vs. non-malleability
- 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
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)
