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

DOI10.1016/J.JCSS.2010.06.013MaRDI QIDQ619913zbMATH OpenOpenAlexFDO

Authors 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

algebraic complexitydiscrepancyextractors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Lower bounds on arithmetic circuits via partial derivatives
• Extractors for circuit sources
• Separation of multilinear circuit and formula size
• Arithmetic circuit lower bounds via MaxRank
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Cites work

• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• A lower bound on the number of additions in monotone computations
• A sum-product estimate in finite fields, and applications
• Balancing syntactically multilinear arithmetic circuits
• Communication Complexity
• ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
• Extracting Randomness Using Few Independent Sources
• Extractors for a constant number of polynomially small MIN-entropy independent sources
• Extractors with weak random seeds
• Fast Parallel Computation of Polynomials Using Few Processors
• scientific article; zbMATH DE number 3692645 (Why is no real title available?)
• Lower bounds on arithmetic circuits via partial derivatives
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Multilinear formulas and skepticism of quantum computing
• Negation can be exponentially powerful
• On the depth complexity of formulas
• On the P versus NP intersected with co-NP question in communication complexity
• Results on communication complexity classes
• Separation of multilinear circuit and formula size
• Simulating independence
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(15)

• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• Tropical complexity, Sidon sets, and dynamic programming
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Lower bounds for monotone counting circuits
• Lower bounds for tropical circuits and dynamic programs
• Monotone circuit lower bounds from robust sunflowers
• Shadows of Newton polytopes
• Monotone arithmetic complexity of graph homomorphism polynomials
• Monotone classes beyond VNP
• Notes on Boolean read-k and multilinear circuits
• Two-source and affine non-malleable extractors for small entropy
• Monotone classes beyond VNP
• Building above read-once polynomials: identity testing and hardness of representation
• Monotone bounded-depth complexity of homomorphism polynomials
• Low-degree polynomials are good extractors

This page was built for publication: Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619913)