Rutgers/DIMACS Theory of Computing Seminar
Spring 2017
Place: CoRE 301
Time: Wednesdays 11:00 am --
12:00 Noon
Organizers: Pranjal Awasthi and Swastik Kopparty
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 18 |
Muthuramakrishnan Venkitasubramaniam University of
Rochester |
TALK CANCELLED |
January 25 |
Matt Weinberg Princeton University |
Simultaneous
Communication Complexity of Two-Player Combinatorial Auctions We consider simultaneous protocols for the following
communication problem: Alice and Bob each have some list of subsets of [m],
A_1,...,A_a, and B_1,...,B_b,
and wish to either: (Allocation Problem): partition [m] into A \sqcup B in order to maximize \max_i
{A \cap A_i} + \max_j {B
\cap B_j}. (Decision Problem): decide whether there exists an i, j, such that A_i \cup B_ j \geq C. For interactive protocols, a (tight)
3/4-approximation is known in poly(m) communication for
both problems. We show the following: - A randomized, simultaneous protocol with O(m) communication that achieves a (tight)
3/4-approximation for the allocation problem. - No randomized, simultaneous protocol with subexponential (in m) communication guarantees better
than a 3/4-1/108 approximation for the decision problem. I'll further discuss the implications of these
results for truthful combinatorial auctions due to a recent result of Dobzinski [FOCS 16]. Joint work with Mark Braverman
and Jieming Mao. |
February 1 |
Clement Cannone Columbia University |
Alice
and Bob Show Distribution Testing Lower Bounds (They don’t talk to each other anymore.) We present a new
methodology for proving distribution testing lower bounds, establishing a
connection between distribution testing and the simultaneous message passing
(SMP) communication model. Extending the framework of Blais,
Brody, and Matulef [BBM12], we show a simple way to
reduce (private-coin) SMP problems to distribution testing problems. This method
allows us to prove several new distribution testing lower bounds, as well as
to provide simple proofs of known lower bounds. Our main result is
concerned with testing identity to a specific distribution p, given as a
parameter. In a recent and influential work, Valiant and Valiant [VV14]
showed that the sample complexity of the aforementioned problem is closely
related to the 2/3-quasinorm of p. We obtain alternative bounds on the
complexity of this problem in terms of an arguably more intuitive measure and
using simpler proofs. More specifically, we prove that the sample complexity
is essentially determined by a fundamental operator in the theory of
interpolation of Banach spaces, known as Peetre's K-functional. We show that this quantity is
closely related to the size of the effective support of p (loosely speaking,
the number of supported elements that constitute the vast majority of the
mass of p). This result, in turn, stems from an unexpected connection to
functional analysis and refined concentration of measure inequalities, which
arise naturally in our reduction. Joint work with
Eric Blais (University of Waterloo) and Tom Gur (Weizmann
Institute) |
February 8 |
Yash Kanoria Columbia University |
Communication
requirements and Informative signaling in matching markets We study the amount
of communication needed to fi nd a stable matching
in a two-sided matching market with private preferences when agents have some
knowledge of the preference distribution. In a two-sided market with workers
and fi rms, when the preferences of workers are
arbitrary and private and the preferences of firms follow an additively
separable latent utility model with commonly known and heterogeneous
parameters, we describe an algorithm that fi nds a
stable matching with high probability and requires at most O*(\sqrt{n})
bits of communication per agent. (We also show that this is the best possible
under this setting.) Our algorithm is a modification of worker-proposing
deferred acceptance that skips wasteful applications. Firms help workers
better target applications by signaling workers that they privately like and
broadcasting to the market a qualifi cation
requirement to discourage those with no realistic chances from applying. Our
results yield insights on how matching markets can be better organized to
reduce congestion. Broadly, agents should reach out to their favorites among
"gettable" partners, while waiting for their dream matches to reach
out to them. Joint work with Itai Ashlagi, Mark Braverman and Peng Shi. |
February 15 |
Muthuramakrishnan Venkitasubramaniam University of Rochester |
Equivocating
Yao: Constant-Rounds Adaptively Secure Multiparty Computation in the Plain
Model Yao’s circuit garbling scheme is one of the basic
building blocks of cryptographic protocol design. Originally designed to
enable two-message, two-party secure computation, the scheme has been
extended in many ways and has innumerable applications. Still, a basic
question has remained open throughout the years: Can the scheme be extended
to guarantee security in the face of an adversary that corrupts both parties,
adaptively, as the computation proceeds? We provide a positive answer to this question. We
define a new type of encryption, called functionally equivocal encryption
(FEE), and show that when Yao’s scheme is implemented with an FEE as the
underlying encryption mechanism, it becomes secure against such adaptive
adversaries. We then show how to implement FEE from any one way function. Combining our scheme with non-committing encryption,
we obtain the first two-message, two-party computation protocol, and the
first constant-rounds multiparty computation protocol, in the plain model,
that are secure against semi-honest adversaries who can adaptively corrupt
all parties. We also provide extensions to the multiparty setting (with
UC-security) and applications to leakage resilience. |
February
22 |
NO SEMINAR |
Mass absences |
March 1 |
Avishay Tal IAS |
Time-Space Hardness of Learning
Sparse Parities How can one
learn a parity function, i.e., a function of the form $f(x) = a_1 x_1 + a_2
x_2 + ... + a_n x_n (mod
2)$ where a_1, ..., a_n
are in {0,1}, from random examples? One
approach is to gather O(n) random examples and
perform Gaussian-elimination. This requires a memory of size O(n^2) and poly(n) time. Another approach is to go over
all possible 2^n parity functions and to verify them by checking O(n) random examples for each guess. This requires a
memory of size O(n), but O(2^n * n) time. In a
recent work, Raz [FOCS, 2016] shows that if an
algorithm has memory of size much smaller than n^2, then it has to spend
exponential time in order to learn a parity function. In other words, fast
learning requires good memory. In this
work, we show that even if the parity function is known to be extremely
sparse, where only log(n) of the a_i's
are nonzero, then the learning task is still time-space hard. That is, we
show that any algorithm with linear size memory and polynomial time fails to
learn log(n)-sparse parities. Consequently,
the classical tasks of learning linear-size DNF formulae, linear-size
decision trees, and logarithmic-size juntas are all time-space hard. Based on
joint work with Gillat Kol
and Ran Raz. |
March 8 |
Afonso Bandeira NYU |
On Phase
Transitions for Spiked Random Matrix and Tensor Models A central problem of random matrix theory is to
understand the eigenvalues of spiked random matrix models, in which a
prominent eigenvector (or low rank structure) is planted into a random
matrix. These distributions form natural statistical models for principal
component analysis (PCA) problems throughout the sciences, where the goal is
often to recover or detect the planted low rank structured. In this talk we
discuss fundamental limitations of statistical methods to perform these tasks
and methods that outperform PCA at it. Emphasis will be given to low rank
structures arising in Synchronization problems. Time permitting, analogous results for spiked tensor
models will also be discussed. Joint work with: Amelia Perry, Alex Wein, and Ankur Moitra. |
March 15 |
NO
SEMINAR |
SPRING BREAK |
March 22 |
Matt Anderson Union College |
Solving Linear
Programs without Breaking Abstractions We draw connections between descriptive complexity theory
and combinatorial optimization to show that the ellipsoid method for solving
linear programs can be implemented in a way that respects the abstractions
and symmetry of the program being solved. That is to say, there is an
algorithmic implementation of the method that does not distinguish, or make
choices, between variables or constraints in the program unless they are
distinguished by properties definable from the linear program. In particular, we demonstrate that the solvability of
linear programs can be expressed in fixed-point logic with counting (FPC) as
long as the program is given by a separation oracle that is itself definable
in FPC. We use this to show that the size of a maximum matching in a graph is
definable in FPC. This refutes a conjecture first posed by Blass, Gurevich and Shelah
(1999). On the way to defining a
suitable separation oracle for the maximum matching program, we provide FPC
formulas defining canonical maximum flows and minimum cuts in undirected
weighted graphs. This is joint work
with Anuj Dawar. |
March 29 |
NO SEMINAR |
IMPROMPTU DEPARTMENT FACULTY MEETING |
April 5 |
Mark Bun Princeton University |
A Nearly
Optimal Lower Bound on the Approximate Degree of AC^0 The approximate degree of a Boolean function f is
the least degree of a real polynomial that approximates f pointwise to error
at most 1/3. For any constant delta > 0, we exhibit an AC^0 function of
approximate degree Omega(n^{1-delta}). This improves
over the best previous lower bound of Omega(n^{2/3})
due to Aaronson and Shi, and nearly matches the trivial upper bound of n that
holds for any function. We accomplish this by giving a generic method for
increasing the approximate degree of a given function, while preserving its
computability by constant-depth circuits. We will also describe several
applications to communication complexity and cryptography. This is joint work with Justin Thaler
and is available at https://eccc.weizmann.ac.il/report/2017/051/. |
April 12 |
Fabrice Benhamouda IBM Research |
Optimization of
Bootstrapping in Circuits In 2009, Gentry proposed the first Fully Homomorphic
Encryption (FHE) scheme, an extremely powerful cryptographic primitive that enables
to perform computations, i.e., to evaluate circuits, on encrypted data
without decrypting them first. This has many applications, particularly in
cloud computing. In all currently known FHE schemes, encryptions are
associated with some (non-negative integer)
noise level. At each evaluation of an AND gate, this noise level increases. This increase is
problematic because decryption succeeds only if the noise level stays below
some maximum level L at every gate of the circuit. To ensure that property,
it is possible to perform an operation called bootstrapping to reduce the
noise level. Though critical, boostrapping is a
time-consuming operation. This expense motivates a new
problem in discrete optimization: minimizing the number of bootstrappings in a circuit while still controlling the
noise level. In this paper, we (1) formally define the bootstrap
problem, (2) design a polynomial-time L-approximation algorithm using a novel
method of rounding of a linear program, and (3) show a matching hardness result:
(L − ε)-inapproximability for any ε > 0. Joint work with Tancrède Lepoint, Claire Mathieu, and Hang Zhou. |
April 19 |
Antigoni Polychroniadou Cornell Tech |
Lower Bounds
for Information-Theoretic Secure Computation Information-Theoretic (IT) secure cryptography
provides unconditional security without the need for unproven complexity
assumptions. The techniques used in IT secure protocols tend to be
computationally much more efficient than the cryptographic machinery needed
for computational security. Therefore, IT secure protocols are attractive
from a practical point of view, however they seem to require a lot of
interaction. In this talk, we will present our recent lower
bounds on the communication complexity of secure Multi-Party Computation
protocols in the IT setting. In particular, we show that protocols based on
the traditional secret-sharing design paradigm cannot be significantly
improved with respect to the communication/computational complexity even in the
preprocessing model. |
April 26 |
Aaron Potechin |
Exact tensor
completion with sum-of-squares In the matrix completion problem, we are given some
entries of a matrix and we are asked to fill in the remaining entries. A
canonical example of this problem is the Netflix challenge, where we are
given the ratings of users on some movies and we are asked to predict their
ratings on other movies. While the matrix completion problem is impossible to
solve in general, it can be solved efficiently if the matrix has the
additional structure of being low-rank. In this talk, I will describe how the nuclear norm
minimization method for matrix completion can be viewed in terms of a dual
certificate. I will then describe how this view can be generalized to the
analogous tensor completion problem via the sum-of-squares hierarchy. No
background except for linear algebra will be assumed for this talk. |