Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Submitted by dloring on Mon, 2014-01-06 11:12
Author: 
D. Gavinsky
O. Meir
O. Weinstein
A. Wigderson
Publication: 
Proceedings of Symposium on the Theory of Computing (STOC) 2014, pp. 1-48, 2014.
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-190, pp. 1-48, 2013.
Year: 
2013
Files
File: 
Full version (pdf)

O. Weinstein

Submitted by dloring on Mon, 2014-01-06 11:06
Home Page: 
http://www.cs.columbia.edu/~omri/

O. Meir

Submitted by dloring on Mon, 2014-01-06 11:06
Home Page: 
http://cs.haifa.ac.il/~ormeir/

D. Gavinsky

Submitted by dloring on Mon, 2014-01-06 11:03
Home Page: 
http://users.math.cas.cz/~gavinsky/

Nati's Long View

Submitted by dloring on Mon, 2014-01-06 10:23
Description: 
Nati Linial's 60'th birthday conference, Jerusalem, Israel - December 18, 2013
File: 
Powerpoint

On Derandomizing Algorithms that Err Extremely Rarely

Submitted by dloring on Mon, 2013-11-18 16:18
Author: 
O. Goldreich
A. Wigderson
Publication: 
Proceedings of Symposium on the Theory of Computing (STOC) 2014, pp. 1-21, 2014.
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-152, pp. 1-21, 2013.
Year: 
2013
Files
File: 
Journal version (pdf)

Non-commutative arithmetic circuits with division

Submitted by dloring on Mon, 2013-11-18 16:11
Author: 
P. Hrubes
A. Wigderson
Publication: 
Theory of Computing, vol. 11, pp. 357-393, 2015.
Proceedings of ITCS (Innovations in Theoretical Computer Science) 2014, pp. 49-66, 2014.
Year: 
2014
Files
File: 
Journal version (pdf)

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Submitted by dloring on Thu, 2013-10-10 10:39
Author: 
O. Goldreich
A. Wigderson
Publication: 
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-043, pp. 1-40, 2013.
Year: 
2013
Files
File: 
Journal version (pdf)

Partial Derivatives in Arithmetic Complexity and Beyond

Submitted by avi on Tue, 2013-10-08 11:52
Author: 
X. Chen
N. Kayal
A. Wigderson
Publication: 
Foundations and Trends in Theoretical Computer Science (FTTCS), vol. 6, no. 1-2, pp. 1-138
Year: 
2011
Files
File: 
pdf

Pages

Subscribe to Avi Wigderson RSS