Improved parallel derandomization via finite automata with applications
From MaRDI portal
Cites work
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Algorithmic derandomization via complexity theory
- Algorithms and Data Structures
- Approximating probability distributions using small sample spaces
- Better pseudorandom generators from milder pseudorandom restrictions
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
- Deterministic parallel algorithms for bilinear objective functions
- Efficient computation of sparse structures
- Fooling Gaussian PTFs via local hyperconcentration
- scientific article; zbMATH DE number 107951 (Why is no real title available?)
- scientific article; zbMATH DE number 1256678 (Why is no real title available?)
- Improved algorithms via approximations of probability distributions (extended abstract)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Minimization of ±1 matrices under line shifts
- New approaches to covering and packing problems
- On a set of almost deterministic k-independent random variables
- On construction of \(k\)-wise independent random variables
- On Relating Time and Space to Size and Depth
- On the optimality of the random hyperplane rounding technique for MAX CUT
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Pseudorandom generators for combinatorial shapes
- Pseudorandom generators for regular branching programs
- Pseudorandom generators for unbounded-width permutation branching programs
- Pseudorandom generators for width-3 branching programs
- Pseudorandomness for network algorithms
- Random restrictions and PRGs for PTFs in Gaussian space
- Simple Constructions of Almost k-wise Independent Random Variables
- Solving packing integer programs via randomized rounding with alterations
- Solving some discrepancy problems in NC
- The Fourth Moment Method
- Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
- Weighted pseudorandom generators via inverse analysis of random walks and shortcutting
- Work-efficient parallel derandomization. I: Chernoff-like concentrations via pairwise independence
This page was built for publication: Improved parallel derandomization via finite automata with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322476)
