Organizer(s)  Swastik Kopparty, Shubhangi Saraf  Archive  
Website  http://www.math.rutgers.edu/~sk1233/theoryseminar/S17/ 
Upcoming Talks
Wednesday, April 26th 
Aaron Potechin , Princeton University 
"Exact tensor completion with sumofsquares" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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 lowrank.
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 sumofsquares hierarchy. No background except for linear algebra will be assumed for this talk. 
Past Talks
Wednesday, April 19th 
Antigoni Polychroniadou , Cornell Tech 
"Lower Bounds for InformationTheoretic Secure Computation" 
Time: 11:00 AM 
Location: CoRe 301 
Abstract: InformationTheoretic (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 MultiParty Computation protocols in the IT setting. In particular, we show that protocols based on the traditional secretsharing design paradigm cannot be significantly improved with respect to the communication/computational complexity even in the preprocessing model.

Wednesday, April 12th 
Fabrice Benhamouda , IBM Research 
"Optimization of Bootstrapping in Circuits " 
Time: 11:00 AM 
Location: CoRe 301 
Abstract: 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 (nonnegative 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 timeconsuming 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 polynomialtime Lapproximation 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. 
Wednesday, April 5th 
Mark Bun, Princeton University 
"A Nearly Optimal Lower Bound on the Approximate Degree of AC^0" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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^{1delta}). 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 constantdepth 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/. 
Wednesday, March 22nd 
Matt Anderson , Union College 
"Solving Linear Programs without Breaking Abstractions" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract:
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 fixedpoint 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. 
Wednesday, March 8th 
Afonso Bandeira , NYU 
"On Phase Transitions for Spiked Random Matrix and Tensor Models" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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. 
Wednesday, March 1st 
Avishay Tal , IAS 
"TimeSpace Hardness of Learning Sparse Parities" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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 Gaussianelimination. 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 timespace 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 linearsize DNF formulae, linearsize decision trees, and logarithmicsize juntas are all timespace hard. Based on joint work with Gillat Kol and Ran Raz. 
Wednesday, February 15th 
Muthuramakrishnan Venkitasubramaniam , University of Rochester 
"Equivocating Yao: ConstantRounds Adaptively Secure Multiparty Computation in the Plain Model" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract:
Yao’s circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable twomessage, twoparty 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 noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantrounds multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UCsecurity) and applications to leakage resilience. 
Wednesday, February 8th 
Yash Kanoria, Columbia University 
"Communication requirements and Informative signaling in matching markets" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: We study the amount of communication needed to fi nd a stable matching in a twosided matching market with private preferences when agents have some knowledge of the preference distribution. In a twosided 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 workerproposing 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. 
Wednesday, February 1st 
Clement Cannone, Columbia University 
"Alice and Bob Show Distribution Testing Lower Bounds (They don’t talk to each other anymore.)" 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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 (privatecoin) 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/3quasinorm 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 Kfunctional. 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) 
Wednesday, January 25th 
Matt Weinberg, Princeton University 
"Simultaneous Communication Complexity of TwoPlayer Combinatorial Auctions " 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: 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/4approximation 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/4approximation for the allocation problem.  No randomized, simultaneous protocol with subexponential (in m) communication guarantees better than a 3/41/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. 
Wednesday, January 18th  CANCELLED 
Muthuramakrishnan Venkitasubramaniam, University of Rochester (CANCELLED TODAY!) 
"Equivocating Yao: ConstantRounds Adaptively Secure Multiparty Computation in the Plain Model " 
Time: 11:00 AM 
Location: CoRE 301 
Abstract: Yao’s circuit garbling scheme is one of the basic building blocks of crytographic protocol design. Originally designed to enable twomessage, twoparty 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 noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantrounds multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UCsecurity) and applications to leakage resilience. 