Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
From MaRDI portal
Publication:619913
DOI10.1016/j.jcss.2010.06.013zbMath1209.68382OpenAlexW2116160867MaRDI QIDQ619913
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.013
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Lower bounds for monotone counting circuits ⋮ Shadows of Newton polytopes ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Monotone circuit lower bounds from robust sunflowers
Cites Work
- Unnamed Item
- Unnamed Item
- On the P versus NP intersected with co-NP question in communication complexity
- Negation can be exponentially powerful
- Results on communication complexity classes
- A lower bound on the number of additions in monotone computations
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Lower bounds on arithmetic circuits via partial derivatives
- A sum-product estimate in finite fields, and applications
- Balancing syntactically multilinear arithmetic circuits
- Extractors for a constant number of polynomially small min-entropy independent sources
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- Fast Parallel Computation of Polynomials Using Few Processors
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Multilinear formulas and skepticism of quantum computing
- Extractors with weak random seeds
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- On the depth complexity of formulas
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Communication Complexity
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
- Extracting Randomness Using Few Independent Sources
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Simulating independence
