Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Aaron Potechin:

TR16-058 | 12th April 2016
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.
This yields a nearly tight ... more >>>

TR12-185 | 29th December 2012
Siu Man Chan, Aaron Potechin

Tight Bounds for Monotone Switching Networks via Fourier Analysis

We prove tight size bounds on monotone switching networks for the NP-complete problem of
$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for
the P-complete problem of generation. This gives alternative proofs of the separations of m-NC
from m-P and of m-NC$^i$ from ... more >>>

TR09-142 | 17th December 2009
Aaron Potechin

Bounds on Monotone Switching Networks for Directed Connectivity

Revisions: 1

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$

more >>>

ISSN 1433-8092 | Imprint