Explicit directional affine extractors and improved hardness for linear branching programs
From MaRDI portal
Cites work
- 3.1 n − o ( n ) circuit lower bounds for explicit functions
- A better-than-3n lower bound for the circuit complexity of an explicit function
- A Lower Bound for Integer Multiplication with Read-Once Branching Programs
- A note on read-k times branching programs
- A simple function that requires exponential size read-once branching programs
- A very simple function that requires exponential size read-once branching programs.
- Affine extractors for almost logarithmic entropy
- Affine extractors over prime fields
- Almost \(k\)-wise independence and hard Boolean functions.
- An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers
- Entropy of contact circuits and lower bounds on their complexity
- Expanders and dimensional expansion
- Expansion in SL₂( R) and monotone expanders
- Extractors for sum of two sources
- Extractors for sumset sources
- Extractors with weak random seeds
- Hardness against linear branching programs and more
- scientific article; zbMATH DE number 3890736 (Why is no real title available?)
- scientific article; zbMATH DE number 3919835 (Why is no real title available?)
- scientific article; zbMATH DE number 1405644 (Why is no real title available?)
- Improved non-malleable extractors, non-malleable codes and independent source extractors
- Linear branching programs and directional affine extractors
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Non-malleable codes and extractors for small-depth circuits, and affine functions
- Non-malleable extractors, two-source extractors and privacy amplification
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- On the complexity of branching programs and decision trees for clique functions
- Optimal testing of Reed-Muller codes
- Randomness extraction in \(\mathsf{AC}^0\) and with small locality
- Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Simulating independence
- The complexity of DNF of parities
- Two source extractors for asymptotically optimal entropy, and (many) more
- Two structural results for low degree polynomials and applications
Cited in
(3)
This page was built for publication: Explicit directional affine extractors and improved hardness for linear branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866487)
