Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
type: Item
instance of: scholarly article
title: Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
zbMATH Open document ID: 1209.68382
author: Ran Raz
author: Amir Yehudayoff
published in: Journal of Computer and System Sciences
publication date: 2011-01-18T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5838483
zbMATH Keywords: algebraic complexity
zbMATH Keywords: discrepancy
zbMATH Keywords: extractors
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.06.013
OpenAlex ID: W2116160867
cites work: Multilinear formulas and skepticism of quantum computing
cites work: Extracting Randomness Using Few Independent Sources
cites work: Simulating independence
cites work: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
cites work: MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
cites work: ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
cites work: A sum-product estimate in finite fields, and applications
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: Some Exact Complexity Results for Straight-Line Computations over Semirings
cites work: On the P versus NP intersected with co-NP question in communication complexity
cites work: Communication Complexity
cites work: Results on communication complexity classes
cites work: Lower bounds on arithmetic circuits via partial derivatives
cites work: Extractors for a constant number of polynomially small min-entropy independent sources
cites work: Multi-linear formulas for permanent and determinant are of super-polynomial size
cites work: Q3002768
cites work: Extractors with weak random seeds
cites work: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
cites work: Balancing syntactically multilinear arithmetic circuits
cites work: A lower bound on the number of additions in monotone computations
cites work: A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
cites work: On the depth complexity of formulas
cites work: Q3886860
cites work: A direct version of Shamir and Snir's lower bounds on monotone circuit depth
cites work: Negation can be exponentially powerful
cites work: Fast Parallel Computation of Polynomials Using Few Processors
DOI: 10.1016/J.JCSS.2010.06.013
description: scientific article; zbMATH DE number 5838483