
We investigate the odd multiway node (edge) cut problem where the input is a
graph with a specified collection of terminal nodes and the goal is to find a
smallest subset of nonterminal nodes (edges) to delete so that the terminal
nodes do not have an odd length path between them. In an earlier work,
Lokshtanov and Ramanujan showed that both odd multiway node cut and odd
multiway edge cut are fixedparameter tractable (FPT) when parameterized by the
size of the solution in undirected graphs. In this work, we focus on directed
acyclic graphs (DAGs) and design a fixedparameter algorithm. Our main
contribution is a broadening of the shadowremoval framework to address parity
problems in DAGs. We complement our FPT results with tight approximability as
well as polyhedral results for 2 terminals in DAGs. Additionally, we show
inapproximability results for odd multiway edge cut in undirected graphs even
for 2 terminals.

Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (STOC
`98) to give the first sublinear time algorithm for the capproximate nearest
neighbor (ANN) problem using only polynomial space. At a high level, an LSH
family hashes "nearby" points to the same bucket and "far away" points to
different buckets. The quality of measure of an LSH family is its LSH exponent,
which helps determine both query time and space usage.
In a seminal work, Andoni and Indyk (FOCS `06) constructed an LSH family
based on random ball partitioning of space that achieves an LSH exponent of
1/c^2 for the l_2 norm, which was later shown to be optimal by Motwani, Naor
and Panigrahy (SIDMA `07) and O'Donnell, Wu and Zhou (TOCT `14). Although
optimal in the LSH exponent, the ball partitioning approach is computationally
expensive. So, in the same work, Andoni and Indyk proposed a simpler and more
practical hashing scheme based on Euclidean lattices and provided computational
results using the 24dimensional Leech lattice. However, no theoretical
analysis of the scheme was given, thus leaving open the question of finding the
exponent of lattice based LSH.
In this work, we resolve this question by showing the existence of lattices
achieving the optimal LSH exponent of 1/c^2 using techniques from the geometry
of numbers. At a more conceptual level, our results show that optimal LSH space
partitions can have periodic structure. Understanding the extent to which
additional structure can be imposed on these partitions, e.g. to yield low
space and query complexity, remains an important open problem.

The spectra of signed matrices have played a fundamental role in social
sciences, graph theory, and control theory. In this work, we investigate the
computational problems of identifying symmetric signings of matrices with
natural spectral properties. Our results are twofold:
1. We show NPcompleteness for the following three problems: verifying
whether a given matrix has a symmetric signing that is positive
semidefinite/singular/has bounded eigenvalues. However, we also illustrate
that the complexity could substantially differ for input matrices that are
adjacency matrices of graphs.
2. We exhibit a stark contrast between invertibility and the abovementioned
spectral properties: we show a combinatorial characterization of matrices with
invertible symmetric signings and design an efficient algorithm using this
characterization to verify whether a given matrix has an invertible symmetric
signing. Next, we give an efficient algorithm to solve the search problem of
finding an invertible symmetric signing for matrices whose support graph is
bipartite. We also provide a lower bound on the number of invertible symmetric
signed adjacency matrices. Finally, we give an efficient algorithm to find a
minimum increase in support of a given symmetric matrix so that it has an
invertible symmetric signing.
We use combinatorial and spectral techniques in addition to classic results
from matching theory. Our combinatorial characterization of matrices with
invertible symmetric signings might be of independent interest.

The computational complexity of multicutlike problems may vary significantly
depending on whether the terminals are fixed or not. In this work we present a
comprehensive study of this phenomenon in two types of cut problems in directed
graphs: double cut and bicut.
1. The fixedterminal edgeweighted double cut is known to be solvable
efficiently. We show a tight approximability factor of $2$ for the
fixedterminal nodeweighted double cut. We show that the global nodeweighted
double cut cannot be approximated to a factor smaller than $3/2$ under the
Unique Games Conjecture (UGC).
2. The fixedterminal edgeweighted bicut is known to have a tight
approximability factor of $2$. We show that the global edgeweighted bicut is
approximable to a factor strictly better than $2$, and that the global
nodeweighted bicut cannot be approximated to a factor smaller than $3/2$ under
UGC.
3. In relation to these investigations, we also prove two results on
undirected graphs which are of independent interest. First, we show
NPcompleteness and a tight inapproximability bound of $4/3$ for the
nodeweighted $3$cut problem. Second, we show that for constant $k$, there
exists an efficient algorithm to solve the minimum $\{s,t\}$separating $k$cut
problem.
Our techniques for the algorithms are combinatorial, based on LPs and based
on enumeration of approximate mincuts. Our hardness results are based on
combinatorial reductions and integrality gap instances.

A $k$lift of an $n$vertex base graph $G$ is a graph $H$ on $n\times k$
vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices
$v_1,\cdots{},v_k$ and each edge $(u,v)$ in $G$ is replaced by a matching
representing a bijection $\pi_{uv}$ so that the edges of $H$ are of the form
$(u_i,v_{\pi_{uv}(i)})$. Lifts have been studied as a means to efficiently
construct expanders. In this work, we study lifts obtained from groups and
group actions. We derive the spectrum of such lifts via the representation
theory principles of the underlying group. Our main results are:
(1) There is a constant $c_1$ such that for every $k\geq 2^{c_1nd}$, there
does not exist an abelian $k$lift $H$ of any $n$vertex $d$regular base graph
with $H$ being almost Ramanujan (nontrivial eigenvalues of the adjacency matrix
at most $O(\sqrt{d})$ in magnitude). This can be viewed as an analogue of the
wellknown noexpansion result for abelian Cayley graphs.
(2) A uniform random lift in a cyclic group of order $k$ of any $n$vertex
$d$regular base graph $G$, with the nontrivial eigenvalues of the adjacency
matrix of $G$ bounded by $\lambda$ in magnitude, has the new nontrivial
eigenvalues also bounded by $\lambda+O(\sqrt{d})$ in magnitude with probability
$1ke^{\Omega(n/d^2)}$. In particular, there is a constant $c_2$ such that for
every $k\leq 2^{c_2n/d^2}$, there exists a lift $H$ of every Ramanujan graph in
a cyclic group of order $k$ with $H$ being almost Ramanujan. We use this to
design a quasipolynomial time algorithm to construct almost Ramanujan
expanders deterministically.
The existence of expanding lifts in cyclic groups of order $k=2^{O(n/d^2)}$
can be viewed as a lower bound on the order $k_0$ of the largest abelian group
that produces expanding lifts. Our results show that the lower bound matches
the upper bound for $k_0$ (upto $d^3$ in the exponent).

Stabilization of graphs has received substantial attention in recent years
due to its connection to game theory. Stable graphs are exactly the graphs
inducing a matching game with nonempty core. They are also the graphs that
induce a network bargaining game with a balanced solution. A graph with
weighted edges is called stable if the maximum weight of an integral matching
equals the cost of a minimum fractional weighted vertex cover. If a graph is
not stable, it can be stabilized in different ways. Recent papers have
considered the deletion or addition of edges and vertices in order to stabilize
a graph. In this work, we focus on a finegrained stabilization strategy,
namely stabilization of graphs by fractionally increasing edge weights. We show
the following results for stabilization by minimum weight increase in edge
weights (min additive stabilizer): (i) Any approximation algorithm for min
additive stabilizer that achieves a factor of $O(V^{1/24\epsilon})$ for
$\epsilon>0$ would lead to improvements in the approximability of
densest$k$subgraph. (ii) Min additive stabilizer has no $o(\log{V})$
approximation unless NP=P. Results (i) and (ii) together provide the first
superconstant hardness results for any graph stabilization problem. On the
algorithmic side, we present (iii) an algorithm to solve min additive
stabilizer in factorcritical graphs exactly in polytime, (iv) an algorithm to
solve min additive stabilizer in arbitrarygraphs exactly in time exponential
in the size of the Tutte set, and (v) a polytime algorithm with approximation
factor at most $\sqrt{V}$ for a superclass of the instances generated in our
hardness proofs.

Motivated by the structural analogies between point lattices and linear
errorcorrecting codes, and by the mature theory on locally testable codes, we
initiate a systematic study of local testing for membership in lattices.
Testing membership in lattices is also motivated in practice, by applications
to integer programming, error detection in latticebased communication, and
cryptography.
Apart from establishing the conceptual foundations of lattice testing, our
results include the following:
1. We demonstrate upper and lower bounds on the query complexity of local
testing for the wellknown family of code formula lattices. Furthermore, we
instantiate our results with code formula lattices constructed from ReedMuller
codes, and obtain nearlytight bounds.
2. We show that in order to achieve low query complexity, it is sufficient to
design onesided nonadaptive canonical tests. This result is akin to, and
based on an analogous result for errorcorrecting codes due to BenSasson et
al. (SIAM J. Computing 35(1) pp121).

Lattices are discrete mathematical objects with widespread applications to
integer programs as well as modern cryptography. A fundamental problem in both
domains is the Closest Vector Problem (popularly known as CVP). It is
wellknown that CVP can be easily solved in lattices that have an orthogonal
basis \emph{if} the orthogonal basis is specified. This motivates the
orthogonality decision problem: verify whether a given lattice has an
orthogonal basis. Surprisingly, the orthogonality decision problem is not known
to be either NPcomplete or in P.
In this paper, we focus on the orthogonality decision problem for a
wellknown family of lattices, namely ConstructionA lattices. These are
lattices of the form $C+q\mathbb{Z}^n$, where $C$ is an errorcorrecting
$q$ary code, and are studied in communication settings. We provide a complete
characterization of lattices obtained from binary and ternary codes using
ConstructionA that have an orthogonal basis. We use this characterization to
give an efficient algorithm to solve the orthogonality decision problem. Our
algorithm also finds an orthogonal basis if one exists for this family of
lattices. We believe that these results could provide a better understanding of
the complexity of the orthogonality decision problem for general lattices.

In a breakthrough work, MarcusSpielmanSrivastava recently showed that every
$d$regular bipartite Ramanujan graph has a 2lift that is also $d$regular
bipartite Ramanujan. As a consequence, a straightforward iterative bruteforce
search algorithm leads to the construction of a $d$regular bipartite Ramanujan
graph on $N$ vertices in time $2^{O(dN)}$. Shift $k$lifts studied by
AgarwalKollaMadan lead to a natural approach for constructing Ramanujan
graphs more efficiently. The number of possible shift $k$lifts of a
$d$regular $n$vertex graph is $k^{nd/2}$. Suppose the following holds for
$k=2^{\Omega(n)}$:
There exists a shift $k$lift that maintains the Ramanujan property of
$d$regular bipartite graphs on $n$ vertices for all $n$. (*)
Then, by performing a similar bruteforce search algorithm, one would be able
to construct an $N$vertex bipartite Ramanujan graph in time $2^{O(d\,log^2
N)}$. Furthermore, if (*) holds for all $k \geq 2$, then one would obtain an
algorithm that runs in $\mathrm{poly}_d(N)$ time. In this work, we take a first
step towards proving (*) by showing the existence of shift $k$lifts that
preserve the Ramanujan property in $d$regular bipartite graphs for $k=3,4$.

The cutting plane approach to optimal matchings has been discussed by several
authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland
'85, Lovasz and Plummer '86, Trick '87, Fischetti and Lodi '07) and its
convergence has been an open question. We give a cutting plane algorithm that
converges in polynomialtime using only Edmonds' blossom inequalities; it
maintains halfintegral intermediate LP solutions supported by a disjoint union
of odd cycles and edges. Our main insight is a method to retain only a subset
of the previously added cutting planes based on their dual values. This allows
us to quickly find violated blossom inequalities and argue convergence by
tracking the number of odd cycles in the support of intermediate solutions.

We study the problem of learning a most biased coin among a set of coins by
tossing the coins adaptively. The goal is to minimize the number of tosses
until we identify a coin i* whose posterior probability of being most biased is
at least 1delta for a given delta. Under a particular probabilistic model, we
give an optimal algorithm, i.e., an algorithm that minimizes the expected
number of future tosses. The problem is closely related to finding the best arm
in the multiarmed bandit problem using adaptive strategies. Our algorithm
employs an optimal adaptive strategy  a strategy that performs the best
possible action at each step after observing the outcomes of all previous coin
tosses. Consequently, our algorithm is also optimal for any starting history of
outcomes. To our knowledge, this is the first algorithm that employs an optimal
adaptive strategy under a Bayesian setting for this problem. Our proof of
optimality employs tools from the field of Markov games.

We study the problem of answering \emph{$k$way marginal} queries on a
database $D \in (\{0,1\}^d)^n$, while preserving differential privacy. The
answer to a $k$way marginal query is the fraction of the database's records $x
\in \{0,1\}^d$ with a given value in each of a given set of up to $k$ columns.
Marginal queries enable a rich class of statistical analyses on a dataset, and
designing efficient algorithms for privately answering marginal queries has
been identified as an important open problem in private data analysis.
For any $k$, we give a differentially private online algorithm that runs in
time $$ \min{\exp(d^{1\Omega(1/\sqrt{k})}), \exp(d / \log^{.99} d)\} $$ per
query and answers any (possibly superpolynomially long and adaptively chosen)
sequence of $k$way marginal queries up to error at most $\pm .01$ on every
query, provided $n \gtrsim d^{.51} $. To the best of our knowledge, this is the
first algorithm capable of privately answering marginal queries with a
nontrivial worstcase accuracy guarantee on a database of size $\poly(d, k)$
in time $\exp(o(d))$.
Our algorithms are a variant of the private multiplicative weights algorithm
(Hardt and Rothblum, FOCS '10), but using a different lowweight representation
of the database. We derive our lowweight representation using approximations
to the OR function by lowdegree polynomials with coefficients of bounded
$L_1$norm. We also prove a strong limitation on our approach that is of
independent approximationtheoretic interest. Specifically, we show that for
any $k = o(\log d)$, any polynomial with coefficients of $L_1$norm $poly(d)$
that pointwise approximates the $d$variate OR function on all inputs of
Hamming weight at most $k$ must have degree $d^{1O(1/\sqrt{k})}$.

We study integer programming instances over polytopes P(A,b)={x:Ax<=b} where
the constraint matrix A is random, i.e., its entries are i.i.d. Gaussian or,
more generally, its rows are i.i.d. from a spherically symmetric distribution.
The radius of the largest inscribed ball is closely related to the existence of
integer points in the polytope. We show that for m=2^O(sqrt{n}), there exist
constants c_0 < c_1 such that with high probability, random polytopes are
integer feasible if the radius of the largest ball contained in the polytope is
at least c_1sqrt{log(m/n)}; and integer infeasible if the largest ball
contained in the polytope is centered at (1/2,...,1/2) and has radius at most
c_0sqrt{log(m/n)}. Thus, random polytopes transition from having no integer
points to being integer feasible within a constant factor increase in the
radius of the largest inscribed ball. We show integer feasibility via a
randomized polynomialtime algorithm for finding an integer point in the
polytope.
Our main tool is a simple new connection between integer feasibility and
linear discrepancy. We extend a recent algorithm for finding lowdiscrepancy
solutions (LovettMeka, FOCS '12) to give a constructive upper bound on the
linear discrepancy of random matrices. By our connection between discrepancy
and integer feasibility, this upper bound on linear discrepancy translates to
the radius lower bound that guarantees integer feasibility of random polytopes.

A hitting set for a collection of sets is a set that has a nonempty
intersection with each set in the collection; the hitting set problem is to
find a hitting set of minimum cardinality. Motivated by instances of the
hitting set problem where the number of sets to be hit is large, we introduce
the notion of implicit hitting set problems. In an implicit hitting set problem
the collection of sets to be hit is typically too large to list explicitly;
instead, an oracle is provided which, given a set H, either determines that H
is a hitting set or returns a set that H does not hit. We show a number of
examples of classic implicit hitting set problems, and give a generic algorithm
for solving such problems optimally. The main contribution of this paper is to
show that this framework is valuable in developing approximation algorithms. We
illustrate this methodology by presenting a simple online algorithm for the
minimum feedback vertex set problem on random graphs. In particular our
algorithm gives a feedback vertex set of size n(1/p)\log{np}(1o(1)) with
probability at least 3/4 for the random graph G_{n,p} (the smallest feedback
vertex set is of size n(2/p)\log{np}(1+o(1))). We also consider a planted
model for the feedback vertex set in directed random graphs. Here we show that
a hitting set for a polynomialsized subset of cycles is a hitting set for the
planted random graph and this allows us to exactly recover the planted feedback
vertex set.

We determine the thresholds for the number of variables, number of clauses,
number of clause intersection pairs and the maximum clause degree of a kCNF
formula that guarantees satisfiability under the assumption that every two
clauses share at most $\alpha$ variables. More formally, we call these formulas
$\alpha$intersecting and define, for example, a threshold $\mu_i(k,\alpha)$
for the number of clause intersection pairs $i$, such that every
$\alpha$intersecting kCNF formula in which at most $\mu_i(k,\alpha)$ pairs of
clauses share a variable is satisfiable and there exists an unsatisfiable
$\alpha$intersecting kCNF formula with $\mu_m(k,\alpha)$ such intersections.
We provide a lower bound for these thresholds based on the Lovasz Local Lemma
and a nearly matching upper bound by constructing an unsatisfiable kCNF to
show that $\mu_i(k,\alpha) = \tilde{\Theta}(2^{k(2+1/\alpha)})$. Similar
thresholds are determined for the number of variables ($\mu_n =
\tilde{\Theta}(2^{k/\alpha})$) and the number of clauses ($\mu_m =
\tilde{\Theta}(2^{k(1+\frac{1}{\alpha})})$) (see [Scheder08] for an earlier but
independent report on this threshold). Our upper bound construction gives a
family of unsatisfiable formula that achieve all four thresholds
simultaneously.

The Lovasz Local Lemma (LLL) is a powerful result in probability theory that
states that the probability that none of a set of bad events happens is nonzero
if the probability of each event is small compared to the number of events that
depend on it. It is often used in combination with the probabilistic method for
nonconstructive existence proofs. A prominent application is to kCNF
formulas, where LLL implies that, if every clause in the formula shares
variables with at most d <= 2^k/e other clauses then such a formula has a
satisfying assignment. Recently, a randomized algorithm to efficiently
construct a satisfying assignment was given by Moser. Subsequently Moser and
Tardos gave a randomized algorithm to construct the structures guaranteed by
the LLL in a very general algorithmic framework. We address the main problem
left open by Moser and Tardos of derandomizing these algorithms efficiently.
Specifically, for a kCNF formula with m clauses and d <= 2^{k/(1+\eps)}/e for
any \eps\in (0,1), we give an algorithm that finds a satisfying assignment in
time \tilde{O}(m^{2(1+1/\eps)}). This improves upon the deterministic
algorithms of Moser and of MoserTardos with running time m^{\Omega(k^2)} which
is superpolynomial for k=\omega(1) and upon other previous algorithms which
work only for d\leq 2^{k/16}/4. Our algorithm works efficiently for a general
version of LLL under the algorithmic framework of Moser and Tardos, and is also
parallelizable, i.e., has polylogarithmic running time using polynomially many
processors.

Logconcave functions represent the current frontier of efficient algorithms
for sampling, optimization and integration in R^n. Efficient sampling
algorithms to sample according to a probability density (to which the other two
problems can be reduced) relies on good isoperimetry which is known to hold for
arbitrary logconcave densities. In this paper, we extend this frontier in two
ways: first, we characterize convexitylike conditions that imply good
isoperimetry, i.e., what condition on function values along every line
guarantees good isoperimetry? The answer turns out to be the set of
(1/(n1))harmonic concave functions in R^n; we also prove that this is the
best possible characterization along every line, of functions having good
isoperimetry. Next, we give the first efficient algorithm for sampling
according to such functions with complexity depending on a smoothness
parameter. Further, noting that the multivariate Cauchy density is an important
distribution in this class, we exploit certain properties of the Cauchy density
to give an efficient sampling algorithm based on random walks with a mixing
time that matches the current best bounds known for sampling logconcave
functions.

Starshaped bodies are an important nonconvex generalization of convex bodies
(e.g., linear programming with violations). Here we present an efficient
algorithm for sampling a given starshaped body. The complexity of the
algorithm grows polynomially in the dimension and inverse polynomially in the
fraction of the volume taken up by the kernel of the starshaped body. The
analysis is based on a new isoperimetric inequality. Our main technical
contribution is a tool for proving such inequalities when the domain is not
convex. As a consequence, we obtain a polynomial algorithm for computing the
volume of such a set as well. In contrast, linear optimization over starshaped
sets is NPhard.