Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOM GRAPH:
Reports tagged with random graph:
TR05-112 | 12th September 2005
Eran Ofek

On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c \sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose
second largest eigenvalue (in absolute value) is at most $c \sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by
retaining each edge ... more >>>

TR19-068 | 27th April 2019
Shuo Pang

LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

Revisions: 1

We prove resolution lower bounds for $k$-Clique on the Erdos-Renyi random graph $G(n,n^{-{2\xi}\over{k-1}})$ (where $\xi>1$ is constant). First we show for $k=n^{c_0}$, $c_0\in(0,1/3)$, an $\exp({\Omega(n^{(1-\epsilon)c_0})})$ average lower bound on resolution where $\epsilon$ is arbitrary constant.

We then propose the model of $a$-irregular resolution. Extended from regular resolution, this model ... more >>>

TR21-070 | 13th May 2021
Shuo Pang

SOS lower bound for exact planted clique

We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the soft'' version of the problem, where the family ... more >>>

ISSN 1433-8092 | Imprint