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
- Randomness-Efficient Sampling Within NC 1
- The power of natural properties as oracles
- Pseudo-derandomizing learning and approximation
- Paradigms for Unconditional Pseudorandom Generators
- Some games on Turing machines and power from random strings
- On optimal language compression for sets in PSPACE/poly
- ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES
- Some recent results on local testing of sparse linear codes
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- Can we locally compute sparse connected subgraphs?
- On generic complexity of the existential theories
- Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
- On generic complexity of the integer factorization problem
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
- Hardness self-amplification: simplified, optimized, and unified
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Nearly optimal pseudorandomness from hardness
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Randomized and Symmetric Catalytic Computation
- On the generic complexity of the problem of computing the Euler function
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Book review of: Inevitable randomness in discrete mathematics, by József Beck
- A characterization of approximation resistance for even \(k\)-partite CSPs
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)
