We study vertex cut and flow sparsifiers that were recently introduced by
Moitra, and Leighton and Moitra. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best known existential upper bound. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we prove a lower bound of Ω(log k/log log k)^{1/2} for flow sparsifiers and a lower bound of Ω(log^{1/2} k/log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist ~O(log k)^{1/2} cut sparsifiers.
Suppose we are given a metric space X such that every k points in X are D-distortion embeddable into l_{1}. In this paper, we study with which distortion the entire space X embeds into l_{1}.
In this paper we present a new approximation algorithm
for the MAX ACYCLIC SUBGRAPH problem. Given an instance where
the maximum acyclic subgraph contains 1/2 + δ fraction of
all edges, our algorithm finds an acyclic subgraph with
1/2 + Ω(δ/ log n) fraction of all edges.
In this paper we present approximation algorithms for
the maximum constraint satisfaction problem with k
variables in each constraint (MAX k-CSP).
Given a (1 - ε) satisfiable 2CSP our first algorithm
finds an assignment of variables satisfying a 1 - O(sqrt{ε})
fraction of all constraints. The best previously known
result, due to Zwick, was 1 - O(ε^{1/3}).
The second algorithm finds a ck/2^{k} approximation
for the MAX k-CSP problem (where c > 0.44 is an absolute
constant). This result improves the previously best
known algorithm by Hast, which had an approximation
guarantee of Ω(k/(2^{k} log k)).
A Divide and Conquer Algorithm for d-Dimensional Arrangement,
In this paper we present a new approximation algorithm for Unique
Games. For a Unique Game with n vertices and k states,
if a (1 - ε) fraction of all constraints is
satisfiable, the algorithm finds an assignment satisfying a
1-O(ε(log n log k)^{1/2})
fraction of all constraints.
To this end, we introduce new embedding techniques for
rounding semidefinite relaxations of problems with large
domain size.
We present approximation algorithms for unique games. For instances with domain size
k where the optimal solution satisfies 1 - ε fraction of all constraints, our algorithms
satisfy roughly k^{-ε/(2 - ε)} and 1 - O(ε log k) fraction of all constraints. Our
algorithms are based on rounding a natural semidefinite programming relaxation for the problem
and their performance almost matches the integrality gap of this relaxation. Our results are
near-optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms)
would refute the conjecture.
We give O(sqrt{log n})-approximation algorithms for the Min UnCut,
Min 2CNF Deletion, Directed Balanced Separator, and Directed Sparsest
Cut problems. The previously best known algorithms give an O(log
n)-approximation for Min UnCut, Directed Balanced Separator, Directed
Sparsest Cut, and an O(log n log log n)-approximation for Min 2CNF
Deletion.
We also show that the integrality gap of an SDP relaxation of the
Minimum Multicut problem is Ω(log n).
We introduce a new graph parameter, called the Grothendieck constant of a graph.
This parameter is a generalization of the classical Grothendieck constant; and it is
equal to an integrality gap of a certain SDP problem, which has various algorithmic applications.
Our results improve a recent result of Kashin and Szarek on Gram matrices of uniformly bounded functions,
and settle a problem of Megretski and of Charikar and Wirth.
In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.
Communications in Information and Systems, vol. 2, no. 2, pp. 147–166, December 2002.
In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables,
i.e., information inequalities which cannot be reduced to the "basic" inequality I(X : Y |Z) > 0. Our results generalize the inequalities of Z. Zhang and R. Yeung (1998) who found the first examples of non-Shannon-type information inequalities.
We prove the conjecture from Igor Pak's paper The Invariants: New Horizons.
The conjecture states that any tiling of a rectangle by T-tetrominoes
can be transformed to any other tiling by a series of "local
moves". We also show connections between this problem and the "six-vertex
model" (studied in mathematical physics).