rnRutgers/DIMACS
Theory of Computing Seminar
Spring 2015
Place: CoRE 301 (NOTE THE ROOM FOR THIS
SEMESTER)
Time: Wednesdays 11:00 am --
12:00 Noon
Organizers: Swastik Kopparty and Shubhangi Saraf
Directions
For those arriving by train to New Brunswick station, the best way
to get to the seminar room is by Rutgers bus. The directions are available by
clicking here.
For those driving in, the best strategy is to pre-arrange to pick up a parking
tag from one of the organizers upon arrival, and park in lot 64. For directions
to Lot 64, click on this link.
Links
·
The Rutgers discrete
math seminar.
·
Other Math and CS seminars at
Rutgers.
·
Theory of Computing seminars from previous
semesters.
Schedule
January 21 |
Igor Shinkar NYU |
Zero-Fixing Extractors for
Sub-Logarithmic Entropy An (n,k)-bit-fixing
source is a distribution on n bit strings, that is fixed on n-k of the
coordinates, and uniform on the remaining k bits. Explicit constructions of
extractors for bit-fixing sources by Gabizon, Raz and Shaltiel (SICOMP 2006)
and Rao (CCC 2009) extract (1-o(1))k bits for k = polylog(n),
almost matching the probabilistic argument. Intriguingly, unlike other
well-studied sources of randomness, a result of Kamp and Zuckerman (SICOMP
2006) shows that, for any k some small portion of the entropy in an (n,k)-bit-fixing source can be
extracted. Although the extractor does not extract all the entropy, it does
extract log(k)/2 bits. In this work we prove that when the entropy k is
small enough compared to n, this exponential entropy-loss is unavoidable, and
it is impossible to extract more than log(k)/2 bits
from (n,k)-bit-fixing sources. In some sense the
remaining entropy is inaccessible, information theoretically. In fact, our impossibility result holds for what
we call zero-fixing sources. These are bit-fixing sources where the fixed
bits are set to 0. We complement our negative result, by giving an explicit
construction of an (n,k)-zero-fixing
extractor, that outputs Omega(k) bits, even for k = polyloglog(n). Furthermore, we give a construction of an (n,k)-bit-fixing extractor, for
entropy k = (1+o(1))loglog(n), with running time n^polyloglog(n). We also give a new construction of an (n,k)-bit-fixing extractor, for
entropy k = polylog(n) based on multi-source
extractors. Joint work with Gil Cohen |
January 28 |
Grigory Yaroslavtsev U Penn |
Near Optimal
LP Rounding for Correlation Clustering on Complete Graphs Introduced about 10 years ago by Bansal, Blum and
Chawla, correlation clustering has become one of the standard techniques in
machine learning and data mining. This due to several advantages of correlation
clustering as compared to other standard clustering methods (e.g. k-means): -- Correlation clustering only requires
qualitative information about similarities between objects. This makes it
applicable in scenarios such as crowdsourced duplicate finding when
information about similarities between objects is generated by humans. -- Correlation clustering doesn’t require the
number of clusters to be specified in advance, producing the number of
clusters that best fits the data. We give new rounding schemes for the standard
linear programming relaxation of the correlation clustering problem,
achieving approximation factors almost matching the integrality gaps: - For complete graphs our appoximation
is 2.06−ε for a fixed constant ε, which almost matches the previously known
integrality gap of 2. - For complete k-partite graphs our approximation
is 3. We also show a matching integrality gap. - For complete graphs with edge weights satisfying
triangle inequalities and probability constraints, our approximation is 1.5,
and we show an integrality gap of 1.2. Our results improve a long line of work on
approximation algorithms for correlation clustering in complete graphs,
previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman
(JACM'08). In the weighted complete case satisfying triangle inequalities and
probability constraints, the same authors give a 2-approximation; for the
bipartite case, Ailon, Avigdor-Elgrabli,
Liberty and van Zuylen give a 4-approximation
(SICOMP'12). |
February 4 |
Rafael Oliveira Princeton |
Subexponential Size Hitting Sets for Bounded
Depth Multilinear Formulas Derandomization of the Polynomial Identity
Testing problem is one of the most basic and challenging problems in Algebraic
Complexity. Despite much effort, derandomizing PIT
seems to be a hard task even for restricted models of computation, including
small depth circuits computing multilinear
polynomials. In this talk, we give subexponential
size hitting sets for bounded depth multilinear
arithmetic formulas. Using the known relation between black-box PIT and lower
bounds we also obtain lower bounds for these models. We note that better lower bounds are known for these
models, but also that none of these bounds was achieved via construction of a
hitting set. Moreover, no lower bound that implies such PIT results, even in
the white-box model, is currently known. Our results are combinatorial in nature and rely
on reducing the underlying formula, first to a depth-4 formula, and then to a
read-once algebraic branching program (from depth-3 formulas we go straight
to read-once algebraic branching programs). Joint work with Amir Shpilka
and Ben Lee Volk, from Tel Aviv University. |
February 11 |
Alex Nikolov MSR/U Toronto |
Randomized
Rounding for the Largest j-Simplex Problem The maximum volume j-simplex problem asks to
compute the j-dimensional simplex of maximum volume inside the convex hull of
a given set of n points in d-dimensional space. This is a natural problem
with long history in computational geometry, and falls in the class of
problems of approximating an arbitrary body with a simpler one. We give a
deterministic approximation algorithm which achieves an approximation ratio
of e^{j/2 + o(j)} and runs in time polynomial in d
and n. The problem is known to be NP-hard to approximate within a factor of c^j for some constant c. Our algorithm also approximates
the problem of finding the largest determinant principal j-by-j submatrix of
a positive semidefinite matrix, with approximation
ratio e^{j +
o(j)}. This latter problem has connections with discrepancy theory and
low-rank matrix approximation. We achieve our approximation by rounding solutions
to a generalization of the D-optimal design problem, or, equivalently, the
dual of an appropriate smallest enclosing ellipsoid problem. |
February 18 |
Sivakanth Gopi Princeton |
2-Server PIR with
sub-polynomial communication A 2-server
Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$'th bit of an $n$-bit database replicated among two
servers (which do not communicate) while not revealing any information about
$i$ to either server. The privacy of the user is
information theoretic and does not rely on any cryptographic assumptions. In
this work we construct a new 2-server PIR scheme with total communication
cost sub polynomial in $n$. This improves over the currently known 2-server
protocols which require $n^{1/3}$ communication and
matches the communication cost of known 3-server PIR schemes. Our improvement
comes from reducing the number of servers in existing protocols, based on
Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing
these protocols in an algebraic way (using polynomial interpolation) and
extending them using partial derivatives. |
February 25 |
NO
SEMINAR |
mass absences |
March 4 |
Stefan Langerman Free University of Brussels |
The Power of
Preprocessing: Detecting and constructing intersections
between geometric objects When solving a computational problem (e.g.,
finding an element in a set), it is often the case that the bulk of the data
used for input for the problem (e.g., the set) is known well in advance. By preprocessing the data (e.g., sorting
the set), it is often possible to significantly reduce the time needed to
solve the problem once the specific query is provided. In this lecture, I will focus on some of the most
fundamental problems in Computational Geometry -- determining if geometric
objects intersect, and if they do what is, or how large is, their
intersection. These problems are fairly well understood in the traditional
setting where two objects are provided and the intersection must be returned
as output. However it may be the case that each object is known long in
advance, and is translated and rotated just prior to the intersection query.
For that setting, I will review some known and new results in an attempt to
determine when preprocessing helps, and when it cannot. |
March
11 |
Michael Forbes IAS |
Polynomial
Identity Testing via Shifted Partial Derivatives In this talk we consider the polynomial identity testing
(PIT) problem: given an algebraic computation which computes a low-degree
multivariate polynomial f, is f identically zero as a polynomial? This problem is of fundamental importance
in computer algebra and also captures problems such as computing matchings in graphs. While this problem has a simple
randomized algorithm (test whether f is zero at a random evaluation point),
it is an active line of pseudorandomness research
to develop efficient deterministic PIT algorithms for interesting models of algebraic
computation. A related problem is to develop lower bounds:
given a model of algebraic computation, find an explicit polynomial f which
is expensive to compute in this model. As efficient deterministic PIT
algorithms for a model of algebraic computation can be shown to imply lower
bounds for that model, developing lower bounds is often a precursor to
developing such PIT algorithms. Recently, a new lower bounds technique called
"the method of shifted partial derivatives" has been introduced and
has been used to obtain a number of new lower bounds for various models,
however its potential for yielding PIT algorithms is largely unexplored. In this work, we use give the first usage of the
method of shifted partial derivatives to develop PIT algorithms. In particular, we will highlight the
relation to divisibility testing questions, that is, testing whether a given
multivariate polynomial f divides another given multivariate polynomial g. |
March 18 |
NO
SEMINAR |
Spring Break |
March 25 |
Tsvi Kopelowitz University of Michigan |
Higher lower
bounds from the 3SUM conjecture The 3SUM hardness conjecture has proven to be a
valuable and popular tool for proving conditional lower bounds on the complexities
of dynamic data structures and graph problems. This line of work was
initiated by Patrascu [STOC 2010] and has received
a lot of recent attention. Most of these lower bounds are based on reductions
from 3SUM to a special set intersection problem introduced by Patrascu, which we call Patrascu's
Problem. However, the framework introduced by Patrascu
that reduces 3SUM to Patrascu's Problem suffers
from some limitations, which in turn produce polynomial gaps between the
achievable lower bounds via this framework and the known upper bounds. We address these issues by providing a tighter and
more versatile framework for proving 3SUM lower bounds via a new reduction to
Patrascu's Problem. Furthermore, our framework does
not become weaker if 3SUM can be solved in truly subquadratic
time, and provides some immediate higher conditional lower bounds for several
problems, including for set intersection data-structures. For some problems,
the new higher lower bounds meet known upper bounds, giving evidence to the
optimality of such algorithms. During the talk, we will discuss this new
framework, and show some new (optimal) lower bounds conditioned on the 3SUM
hardness conjecture. In particular, we will demonstrate how some old and new
triangle listing algorithms are optimal for any graph density, and prove a
conditional lower bound for incremental Maximum Cardinality Matching which
introduces new techniques for obtaining amortized lower bounds. |
April 1 NONSTANDARD TIME!
9:30 am |
Sergey Yekhanin Microsoft |
Kolmogorov width of discrete
linear spaces: an approach to matrix rigidity A square matrix V is called rigid if every matrix
obtained by altering a small number of entries of V has sufﬁciently high rank.
While random matrices are rigid with high probability, no explicit
constructions of rigid matrices are known to date. Obtaining such explicit
matrices would have major implications in computational complexity theory.
One approach to establishing rigidity of a matrix V is to come up with a
property that is satisﬁed by any collection of vectors arising from a
low-dimensional space, but is not satisﬁed by the rows of V even after
alterations. In this work we propose such a candidate property that has the
potential of establishing rigidity of combinatorial design matrices over the
binary ﬁeld. Stated informally, we conjecture that under a suitable embedding
of the Boolean cube into the Euclidian space, vectors arising from a low
dimensional linear space modulo two always have somewhat small Kolmogorov
width, i.e., admit a non-trivial simultaneous approximation by a low
dimensional Euclidean space. This implies rigidity of combinatorial designs,
as their rows do not admit such an approximation even after alterations. Our
main technical contribution is a collection of results establishing weaker
forms and special cases of the conjecture above. (Joint work with Alex Samorodnitsky
and Ilya Shkredov). |
April 8 |
Roy Schwartz Princeton |
Simplex
Partitioning via Exponential Clocks and the Multiway
Cut Problem Multiway Cut is a graph partitioning
problem in which the objective is to find a minimum weight set of edges
disconnecting a special set of vertices called terminals. This problem is
NP-hard and there is a well known geometric relaxation in which the graph is
embedded into a high dimensional simplex. Rounding the geometric relaxation
is equivalent to partitioning the simplex. I will present a simplex
partitioning method that is based on competing exponential clocks and
distortion. Applying this method to Multiway Cut
yields an extremely simple (4/3)-approximation, thus improving the previous
best known algorithm of Karger et al. Further
improvements by a follow-up work will also be discussed along with related
open questions. Joint work with Niv Buchbinder and Joseph (Seffi) Naor. |
April 15 |
Gillat Kol IAS |
Exponential
Separation of Information and Communication In profoundly influential works, Shannon and
Huffman show that if Alice wants to send a message X to Bob, it's sufficient
for her to send roughly H(X) bits (in expectation), where H denotes Shannon's
entropy function. In other words, the message X can be compressed to roughly
H(X) bits, the information content of the message. Can one prove similar
results in the interactive setting, where Alice and Bob engage in an
interactive communication protocol? We show the first gap between communication
complexity and information complexity, by giving an explicit example of a boolean function with information complexity O(k), and distributional communication complexity >
2^k. This shows that a communication protocol cannot always be compressed to
its internal information, answering (the standard formulation of) the above
question in the negative. By a result of Braverman,
our example gives the largest possible gap. By a result of Braverman
and Rao, our example gives the first gap between
communication complexity and amortized communication complexity, implying
that strong direct sum does not hold for distributional communication
complexity, answering a long standing open problem. Joint work with Anat Ganor and Ran Raz. |
April 22 |
Noam Solomon Tel Aviv University |
Incidences between points and
lines and extremal configuration of lines in
Euclidean spaces. In 1983, Szemeredi and
Trotter proved a tight bound for the number of incidences between points and
lines in the plane. Ever since then, incidence geometry has been a very
active research area, bridging between computer science and mathematics, with
many connections to diverse topics, from range searching algorithms to the Kakeya problem. Over 25 years later, Guth
and Katz proved a tight incidence bound for points and lines in three
dimensions. Their proof introduced methods from advanced algebra and
especially from algebraic geometry which were not used in combinatorics
before. This enabled Guth and Katz to (almost)
settle the Erdos distinct distances problem - a
problem which stubbornly stood open for over 60 years, despite very brave
attempts to solve it. The work of Guth and Katz has
given significant added momentum to incidence geometry, making many problems,
deemed hopeless before the breakthrough, amenable to the new techniques. In this talk I will present the area of incidence
geometry, before and after, highlighting the basics of the new ``algebraic''
approach, and will also present very recent results, joint with Micha Sharir, among which we
studied incidences between points and lines in four dimensions, incidences
between points and lines that lie on special surfaces and other related
questions. We will also give a variety of interesting open related questions. |
April 29 |
Sanjeev Arora Princeton |
Random Walks
on Context Spaces: Towards an explanation of the mysteries of semantic word
embeddings Semantic word embeddings represent words as
vectors in R^d for say d=300. They are useful for many NLP
tasks and often constructed using nonlinear/nonconvex
techniques such as deep nets and energy-based models. Recently Mikolov et al (2013) showed that such embeddings exhibit
linear structure that can be used to solve "word analogy tasks"
such as man: woman :: king: ??. Subsequently, Levy and Goldberg (2014) and
Pennington et al (2014) tried to explain why such linear structure should arise in embeddings
derived from nonlinear methods. We
point out gaps in these explanations and provide a more complete explanation
in the form of a loglinear generative model for
text corpora that directly models latent semantic structure in words and
involves random walk in the context space.
A rigorous mathematical analysis is performed to obtain explicit
expressions for word co-occurrance probabilities,
which leads to a surprising explanation for why word embeddings exist and why
they exhibit linear structure that allows solving analogies. Our model and its analysis lead to several
counterintuitive predictions, which are also empirically verified. We think our methodology may be useful in other
settings. Joint work with Yuanzhi
Li, Yingyu Liang, Tengyu
Ma, and Andrej Risteski (listed in alphabetical
order). manuscript at http://arxiv.org/abs/1502.03520 |