193 citations · 274 across the 24 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2019
High-precision Estimation of Random Walks in Small Space
AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh +3
We provide a deterministic -space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within…
cs.CC2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
We prove that with high probability over the choice of a random graph from the Erdős-Rényi distribution , the -time degree Sum-of-Squares semidefinite p…
cs.CC2012★ 193 cited
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this que…