Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors

DOI10.1016/j.jcss.2010.06.013zbMath1209.68382OpenAlexW2116160867MaRDI QIDQ619913

Ran Raz, Amir Yehudayoff

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

zbMATH Keywords

discrepancyalgebraic complexityextractors

Mathematics Subject Classification ID

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