Uriel Feige, Marek Karpinski, Michael Langberg

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the ...
more >>>

Sofya Raskhodnikova, Adam Smith

We show that in the bounded degree model for graph property testing,

adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).

We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Sabyasachi Basu, Akash Kumar, C. Seshadhri

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

Oded Goldreich, Laliv Tauber

Considering the bounded-degree graph model, we show that if the degree bound is two,

then every graph property can be tested within query complexity that only depends on the proximity parameter.

Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.

The key observation is that a ...
more >>>