ﻻ يوجد ملخص باللغة العربية
In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness $epsilon$ and soundness $frac{1}{2}$ is at least as difficult as Small-Set Expansion with completeness $epsilon$ and soundness $f(epsilon)$, for any function $f(epsilon)$ which grows faster than $sqrt{epsilon}$. We achieve this amplification via random walks -- our gadget is the graph with adjacency matrix corresponding to a random walk on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph $G$, a positive integer $r$, and a set $S$ of vertices, approximates the conductance of $S$ in the $r$-step random walk on $G$ to within a factor of $1+epsilon
We provide a deterministic $tilde{O}(log N)$-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error ($epsilon=1/mathrm{poly}(N)$) where $
We study the NP-hard textsc{$k$-Sparsest Cut} problem ($k$SC) in which, given an undirected graph $G = (V, E)$ and a parameter $k$, the objective is to partition vertex set into $k$ subsets whose maximum edge expansion is minimized. Herein, the edge
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khots 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain Grassmanian agreement tester. In this wo
In the $d$-Scattered Set problem we are asked to select at least $k$ vertices of a given graph, so that the distance between any pair is at least $d$. We study the problems (in-)approximability and offer improvements and extensions of known results f