Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with survey:
TR09-077 | 16th September 2009
Zeev Dvir

From Randomness Extraction to Rotating Needles

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

TR11-108 | 8th August 2011
Scott Aaronson

Why Philosophers Should Care About Computational Complexity

Revisions: 2

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

TR14-041 | 31st March 2014
Shachar Lovett

Recent advances on the log-rank conjecture in communication complexity

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this ... more >>>

ISSN 1433-8092 | Imprint