Friday, November 16, 2018,
New York City

The Graduate Center, CUNY

Room 4102 (Science Center, 4^{th} floor)

Antonis Achilleos

Joint work with Luca Aceto, Adrian Francalanza, Anna Ingólfsdóttir, and Karoliina Lehtinen.

slides

Hafiz Asif

(1) study of the limits of differentially private mechanisms for this problem,

(2) conceptualize the idea of privacy in this setting and propose a new definition that generalizes differential privacy,

(3) construct a compiler that transforms differentially private mechanisms into mechanisms private in our sense but with exponentially better utility, and finally

(4) design and evaluate heuristics theoretically and empirically.

Alexandr Andoni

Most surprisingly, the new data structure achieves a O(log d) approximation for an arbitrary norm. The only other such generic approach, via John's ellipsoid, would achieve square-root-d approximation only.

Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten.

Costis Daskalakis

(Based on joint works with Dikkala, Gouleakis, Panageas, Tzamos, and Zampetakis)

Bio: Constantinos Daskalakis is a professor of computer science and electrical engineering at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC Berkeley. His research interests lie in theoretical computer science and its interface with economics, probability, machine learning and statistics. He has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science (Kalai) Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, the 2012 Microsoft Research Faculty Fellowship, the 2015 Research and Development Award by the Vatican Giuseppe Sciacca Foundation, the 2017 Google Faculty Research Award, the 2018 Simons Investigator Award, and the 2018 Rolf Nevanlinna Prize from the International Mathematical Union. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.

Vasilis Gkatzelis

slides

Subhash Khot

Two interesting consequences (among several others) of the theorem are:

(1) Given an n-vertex graph that contains an independent set of size n/4, it is NP-hard to find an independent set of size \eps n where \eps > 0 is an arbitrarily small constant.

One also gets a coloring result: given an (almost) 4-colorable graph, it is NP-hard to (almost) color it with constantly many colors.

(2) It, arguably, gives strong evidence towards the Unique Games Conjecture. In a certain sense, it already goes "half-way" towards proving the Unique Games Conjecture.

This is joint work with Irit Dinur, Guy Kindler, Dor Minzer, and Muli Safra. It appears in a sequence of papers [ECCC Reports TR16-124, TR16-198, TR17-094, TR18-006]. It also benefited from contributions in [K Safra'11], [Barak Kothari Steurer'18], [K Minzer Moshkoviz Safra'18].

slides

Periklis A. Papakonstantinou

Our setting: Fix a number K'< K. In our model we compute by first taking the output of our chosen agent:{0,1}^N -> {0,1}^K'. Then, we consider query access to the input bits of f. We want to understand for which functions f knowing the output of agent does not significantly help in reducing the number of queries (i.e. no intelligent choice of "agent" speeds up the computation).

We develop a lower bounding technique for functions f that are approximations of real multivalued polynomial functions of moderate degree. In particular, we use our framework to prove a strong lower bound in the number of queries needed for computing a rounded version of M^n for a rational valued M in Q^{nxn} via repeated squaring.

Technically: we show how one can handle arbitrary stochastic input correlations that appear in our model. Such correlations appear when the (arbitrary) "agent" function acts on input distributions. We analyze these correlations by identifying probability mass (even for discrete events) as volume in an appropriate space, then considering how volume changes under low-distortion embeddings, and finally we functionally decompose the effect of the agent function which can be thought as a quasi-operator (i.e. the quasi-operator analog of the Fredholm alternative theorem).

Conceptually: one corollary of our matrix powering lower bound is a barrier in the derandomization of randomized logarithmic space (or BPL).

Joint work with Yuanzhi Li and Xin Yang.

Nikos Triandopoulos

In this talk, I will present a new provably secure AAD scheme that supports succinct polylogarithmic proofs, for the first time simultaneously: For a dictionary of size n, lookup and append-only proofs have O(log^2 n) and O(log n) size, respectively. The new construction is based on novel extensions to bilinear accumulators in support of efficient precomputed and dynamically updated subset proofs, which may be of independent interest.

Omri Weinstein

Joint work with Zeev Dvir (Princeton) and Alexander Golovnev (Harvard).

Manolis Zambetakis

Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is universal in the worst-case.

joint work with: Katerina Sotiraki and Giorgos Zirdelis