NYCAC 2018 - Abstracts

Friday, November 16, 2018,   New York City
The Graduate Center, CUNY
Room 4102 (Science Center, 4th floor)

The New York Colloquium on Algorithms and Complexity


Adventures in Monitorability
Antonis Achilleos

I will present recent work on runtime monitorability for the Hennessy-Milner logic with recursion (recHML), a very expressive variant of the modal mu-calculus. We investigate the monitorability of recHML with a linear-time semantics and then compare the obtained results with previous results for the branching-time setting. We observe that the class of monitorable properties exhibits different phenomena for linear time than for branching time. Our work establishes an expressiveness hierarchy of monitorable fragments of recHML in a linear-time setting and exactly identifies what kinds of guarantees can be given using runtime monitors for each fragment in the hierarchy. The proposed framework supports the automatic, compositional synthesis of correct monitors from monitorable properties.

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

Outlier detection and privacy
Hafiz Asif

Outlier detection is a fundamental problem in data analysis. This work initiates the study of privately finding outliers, which means to detect outliers without hurting the privacy of the remaining population in the dataset. We start our study with the basic primitive of an "outlier query"; i.e., determining whether an object is an outlier. In our contribution we
(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.

Spectral partitions for metrics & nearest neighbor search
Alexandr Andoni

We establish a generic reduction from nonlinear spectral gaps of metric spaces to space partitions, in the form of data-dependent Locality-Sensitive Hashing. This yields a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN). Using this reduction, we obtain a new ANN data structure under an arbitrary d-dimensional norm, where the query algorithm makes only a sublinear number of probes into the data structure.
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.

Efficient Statistics from Truncated and Dependent Samples
Costis Daskalakis

Standard statistical estimation assumes access to uncensored and independent data. We present recent work on efficient statistics from censored and dependent data. Our first result is an efficient algorithm for an open problem, going back to Galton, Pearson, and Fisher, of estimating the parameters of a multivariate normal distribution from truncated samples. Truncation is a strong type of censoring, which occurs when samples falling outside of some subset S of the support of the distribution are not observed, and their count in proportion to the observed samples is also not observed. Our second result is an efficient algorithm for linear and logistic regression in settings where the response variables are dependent. Both methods are based on stochastic gradient descent, and use concentration and anticoncentration of measure.

(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.

Cost-Sharing Methods for Scheduling Games under Uncertainty
Vasilis Gkatzelis

We study the performance of cost-sharing protocols in a selfish scheduling setting with load-dependent cost functions. Previous work on selfish scheduling protocols has focused on two extreme models: omnipotent protocols that are aware of every machine and every job that is active at any given time, and oblivious protocols that are aware of nothing beyond the machine they control. The main focus of this talk is on a well-motivated middle-ground model of "resource-aware" protocols, which are aware of the set of machines that the system comprises, but unaware of what jobs are active at any given time. Apart from considering budget-balanced protocols, to which previous work was restricted, we augment the design space by also studying the extent to which overcharging can lead to improved performance.

The 2-to-2 Games Theorem
Subhash Khot

I will present an overview of a recent proof of the 2-to-2 Games Theorem. The proof has two parts: a construction of an appropriate PCP/reduction and a structure theorem about "non-optimally expanding" sets in the Grassmann graph; the latter is used to analyze the "soundness" of the former.
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].

Query complexity for leaky inputs
Periklis A. Papakonstantinou

We consider the following black-box setting for computing f:{0,1}^N -> {0,1}^K, a function with multiple output bits.

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.

Append-only Authenticated Dictionaries with Polylogarithmic Proofs
Nikos Triandopoulos

Append-only authenticated dictionaries (AADs) provide integrity guarantees for a semi-dynamic data set managed by a malicious server: Subject to data digests and lookup and append-only proofs published by the server, a client can verify that a search returns all the values ever stored in the dictionary under a given key. Such authentication functionality has recently attracted interest due to its direct application to transparency logs (e.g., Google's certificate-transparency service offering stronger security for public-key infrastructures). Yet, existing AAD schemes exhibit unbalanced performance, requiring one of the above proofs to be linear in an ever-growing dictionary size.

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.

Static Data Structure Lower Bounds Imply Rigidity
Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t ≥ ω(log^2 n) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space (s = (1+ε)n), would already imply a semi-explicit (P^NP) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy, and Yekhanin, 2009). Our result further asserts that polynomial (t ≥ n^δ) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (which would close a four-decade open question). In the succinct space regime (s = n+o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our main result relies on a new connection between the “inner” and “outer” dimensions of a matrix (Paturi and Pudlak, 2006), and on a new worst-to-average case reduction for rigidity, which is of independent interest.

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

PPP-completeness with Connections to Cryptography
Manolis Zambetakis

PPP is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, prior to our work no complete problem was known for PPP. Our work identifies the first natural PPP-complete problem: constrained-SIS (cSIS), and thus we answer a longstanding open question since[Papadimitriou1994].
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