Rutgers/DIMACS Theory
of Computing Seminar
Fall 2013
Place: CoRE 431
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
|
September 11 |
Aravindan Vijayaraghavan CMU |
Uniqueness of Tensor
Decompositions with Applications to Learning Latent Variable Models We give a robust version of the celebrated result
of Kruskal on the uniqueness of tensor
decompositions: we prove that given a tensor whose decomposition satisfies a
robust form of fairly general condition called the Kruskal's
rank condition, it is possible to recover the terms of the decomposition if
the tensor is known up to a sufficiently small (inverse polynomial) error. Kruskal's theorem has found many
applications in statistics, signal processing, data mining -- in machine
learning, it is used in proving the identifiability
of parameters for various latent variable models and mixture models such as
Hidden Markov models, mixtures of Gaussians etc. Our robust version
immediately implies identifiability using only polynomially many samples in many of these settings.
Given the importance of Kruskal's theorem in the
tensor literature, we expect that this robust version will have several
applications beyond the settings we explore in this work. Based on joint work with Aditya
Bhaskara and Moses Charikar |
|
September 18 |
Rotem Oshman Princeton University Tel Aviv University |
Tight Bounds for Set Disjointness in the Message-Passing Model In many distributed systems, the cost of
computation is dominated by the cost of communication between the machines
participating in the computation. Communication complexity is therefore a
very useful tool in understanding distributed computation, and communication
complexity lower bounds have been used extensively to obtain lower bounds on
various distributed problems. However, almost all applications of
communication complexity lower bounds in distributed computing use two-party
lower bounds, despite the fact that distributed computation usually involves
many players. Unfortunately, there are interesting distributed problems that
it appears cannot be addressed using two-player lower bounds, because
reductions from two-player problems seem to lose the "hardness" of
the problem. With this motivation in mind, in this work we
study communication complexity in the multi-party message-passing model,
which has been extensively used in distributed computing and in secure
multi-party computation. In the message-passing model there are k players,
each with a private n-bit input, and the players communicate with each other
over private channels. We show a lower bound of Omega(n*k)
on the communication complexity of set disjointness
in the message-passing model. To obtain this bound we develop information
complexity tools for the model, prove a direct-sum theorem, and show that the
information complexity of computing a 1-bit AND with k players is Omega(k). This is joint work with Mark Braverman,
Faith Ellen, Toniann Pitassi
and Vinod Vaikuntanathan. |
|
September 25 |
Yevgeniy Dodis NYU |
Key Derivation Without Entropy
Waste We revisit the classical question of converting an
imperfect source X of min-entropy k into a usable m-bit cryptographic key for
some underlying application P. If P has security delta (against some class of
attackers) with a uniformly random m-bit key, we seek to design a key
derivation function (KDF) h that allows us to use R=h(X) as the key for P and
results in comparable security delta' close to delta. Seeded randomness
extractors provide a generic way to solve this problem provided that k > m
+ 2*log(1/delta), and this lower bound on k (called
"RT-bound") is known to be tight in general. Unfortunately, in many
situation the "waste" of 2*log(1/delta) bits of entropy is
significant, motivating the question of designing KDFs with less waste for
important special classes of sources X or applications P.I will discuss
several positive and negative results in this regard. The most surprising of them will be a positive
result for all unpredictability applications P, yielding a provably secure
KDF with entropy "waste" only loglog(1/delta) - an expenential
improvement over the RT-bound. |
|
October 2 |
Xi Chen Columbia University |
Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner
2-Systems We analyze the 2-dimensional Weisfeiler-Leman
(2-dim WL) refinement, an extension of the naive refinement heuristic for
isomorphism testing, over Steiner 2-systems. A Steiner 2 -system consists of
points and lines, where each line passes the same number of points and each
pair of points uniquely determines a line. Each Steiner 2-system induces a
Steiner graph, in which vertices represent lines and edges represent
intersections of lines. Steiner graphs are an important subfamily of strongly
regular graphs whose isomorphism testing has challenged researchers for
years. Inspired by the previous analyses of the individualization and
refinement method by Babai and by Spielman, we show that the individualization of O(log n)
points and lines suffices for the 2-dim WL refinement to distinguish all
pairs of points of a Steiner 2-system. As a result, the isomorphism of
Steiner 2-systems with n lines can be tested in time n^{O(log
n)}, improving the previous best upper bound of exp(\tilde{O}(n^{1/4}))
by Spielman. Before our result, quasipolynomial-time
isomorphism testing was only known for the case when the line size is polylogarithmic, as shown by Babai
and Luks. A result essentially identical to ours was
obtained simultaneously by Babai and Wilmes. They performed a direct analysis of the
individualization and refinement method based on the naive refinement,
building on a different philosophy and combinatorial structure theory. Joint work with Xiaorui
Sun and Shang-Hua Teng. |
|
October 9 |
Noga Alon Tel Aviv University IAS |
Approximation algorithms via
matrix covers I will describe a general technique for obtaining
approximate solutions of hard quadratic optimization problems using
economical covers of high dimensional sets by small cubes. The analysis of
the method leads to intriguing algorithmic, combinatorial, extremal, geometric and probabilistic questions. Based on joint work with Lee, Shraibman
and Vempala. |
|
October 16 |
Brendan Juba Harvard University |
Efficient reasoning in PAC
Semantics Machine learning is often employed as one step in a
larger application, serving to perform information extraction or data mining
for example. The rules obtained by such learning are then used as inputs to a
further analysis. As a consequence of the inputs to this analysis having been
learned, however, its conclusions can only be theoretically guaranteed to
satisfy the same standard as the inputs---that of "PAC Semantics"
(Valiant, 2000). In this talk, we explore the benefits of taking the problems
of learning and logical reasoning together, capturing a relatively general
family of such applications. Briefly, the benefit is that we can
simultaneously (1) handle incomplete information, (2) utilize rules that are
a reasonable but imperfect fit for the data, and (3) reach conclusions more
efficiently than is achieved by known algorithms for reasoning from rules
alone. Precisely, we consider a problem of testing the validity of a
"query" formula (hypothesis) against incomplete data. We present
algorithms for soundly verifying such queries that succeed whenever there
exist learnable rules that suffice to complete a simple proof of the query,
matching what can be achieved by such a two-stage learning and reasoning
process. |
|
October 23 |
Sergey Yekhanin Microsoft Research Silicon Valley |
Local erasure coding for data
storage. Historically, most large distributed storage
systems (e.g., Hotmail) have been using replication to provide reliability
against machine failures. Today however as the amount of stored data reaches
multiple Exabytes keeping few copies of data around
is becoming prohibitively expensive. Therefore more and more systems are
adopting erasure coding in place of replication. Local Reconstruction Codes (LRCs) are a new class
of erasure correcting codes designed specifically for applications in data
storage. Built upon the rich mathematical theory of locally decodable codes
developed in the theory community, LRCs provide high level of reliability and
allow data fragments to be reconstructed quickly in typical failure scenarios.
LRCs have been recently deployed by Windows Azure Storage and are going to
ship in Windows 8.1 and Windows Server 2012. In this talk we will discuss motivation behind
local reconstruction codes and cover the main technical challenges and
tradeoffs in the design of these codes. (Based on joint papers with Brad Calder, Michael
Forbes, Parikshit Gopalan,
Cheng Huang, Bob Jenkins, Jin Li, Aaron Ogus, Huseyin Simitci, and Yikang Xu.) |
|
October 30 |
NO
SEMINAR |
(the
day after FOCS) |
|
November 6 |
Mark Lewko IAS |
Sets of large doubling I will discuss the structure of |
|
November 13 |
Rocco Servedio Columbia University |
Learning from satisfying
assignments We introduce and study a new type of learning problem
for probability distributions over the Boolean hypercube. As in the standard PAC learning model, a
learning problem in our framework is defined by a class C of Boolean
functions over the hypercube, but unlike the standard PAC model, in our model
the learning algorithm is given uniform random satisfying assignments of an
unknown function in C and its goal is to output a high-accuracy approximation
of the uniform distribution over the space of satisfying assignments for f.
This distribution learning problem may be viewed as a demanding variant of
standard Boolean function learning, where the learning algorithm only
receives positive examples and --- more importantly --- must output a
hypothesis function which has small *multiplicative* error (i.e. small error
relative to the size of f^{-1}(1). As our main results, we show that the two most
widely studied classes of Boolean functions in computational learning theory
--- linear threshold functions and DNF formulas --- have efficient
distribution learning algorithms in our model. Our algorithm for linear
threshold functions runs in time poly(n,1/epsilon)
and our algorithm for polynomial-size DNF runs in quasipolynomial
time. On the other hand, we also prove
complementary hardness results which show that under cryptographic
assumptions, learning monotone 2-CNFs, intersections of 2 halfspaces,
and degree-2 PTFs are all hard. This shows that our algorithms are close to
the limits of what is efficiently learnable in this model. Joint work with Anindya
De and Ilias Diakonikolas. |
|
November 20 |
Gillat Kol IAS |
Interactive Channel Capacity In a profoundly influential 1948 paper, Claude
Shannon defined the entropy function H, and showed that the capacity of a symmetric
binary channel with noise rate (bit flip rate) eps
is 1-H(eps). This means
that one can reliably communicate n bits by sending roughly n / (1-H(eps)) bits over this channel. The extensive study of interactive communication
protocols in the last decades gives rise to the related question of finding
the capacity of a noisy channel when it is used interactively. We define
interactive channel capacity as the minimal ratio between the communication
required to compute a function (over a non-noisy channel), and the
communication required to compute the same function over the eps-noisy channel. We show that the interactive channel
capacity is roughly 1-Theta(sqrt(H(eps)) ). Our result gives the first separation between
interactive and non-interactive channel capacity. Joint work with Ran Raz. |
|
November 27 |
NO
SEMINAR |
(the
day before Thanksgiving) |
|
December 4 |
Kostas Bekris Rutgers University |
Algorithmic Challenges in Robot
Motion Planning Motion planning is a prototypical computationally
hard problem, which requires the computation of collision-free, feasible
paths for moving bodies in continuous spaces. Due to its importance in many
applications, such as robotics and computer simulations, a variety of
practical approaches have been developed for solving effectively many
planning instances. A popular methodology samples valid configurations of a
moving body to incrementally construct and connect the nodes of a graph on
which path planning problems are then solved. These methods provide
probabilistic instead of deterministic completeness. A recent development has
been the identification of the conditions under which these methods also
converge asymptotically to optimal paths in continuous configuration spaces. This talk will review the state-of-the-art in
algorithmic motion planning and recent contributions of our research group in
balancing performance guarantees, such as completeness and path quality, and
computational requirements, such as time and memory requirements.
Furthermore, open problems will be identified that motivate further research
in this area. |