Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Separations:
TR15-164 | 13th October 2015
Pavel Hrubes, Amir Yehudayoff

On isoperimetric profiles and computational complexity

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

TR18-010 | 14th January 2018
Alexander A. Sherstov

Algorithmic polynomials

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

ISSN 1433-8092 | Imprint