NYCAC 2015 - Abstracts

Sequentially Composable Rational Proofs
Rosario Gennaro

We show that Rational Proofs do not satisfy basic compositional properties in the case where a large number of "computation problems" are outsourced. We show that a "fast" incorrect answer is more remunerable for the prover, by allowing him to solve more problems and collect more rewards. We present an enhanced definition of Rational Proofs that removes the economic incentive for this strategy and we present a protocol that achieves it for some uniform bounded-depth circuits.
Joint work with Matteo Campanelli.

The Complexity of Resilience and Responsibility for Conjunctive Queries
Neil Immerman

The resilience of a boolean query with respect to a database, D, is the minimum number of tuples that must be removed from D to make the query false. Resilience is crucial in computing the minimum change to a database needed to change the answer of a query or view. We study the complexity of computing resilience for self-join free conjunctive queries. We show that there is a dichotomy: each such problem is NP complete or in P. Furthermore we give a simple and efficiently computable criterion for testing whether a query's resilience is easy or hard. We introduce the concept of a (cyclic) triad. We prove that the resilience of a query is hard iff its dual hypergraph contains a triad. We also show that a similar results hold in the presence of functional dependencies and for the related problem of computing the responsibility of a given tuple towards a query answer.
This work, with coauthors Cibele Freire, Wolfgang Gatterbauer, and Alexandra Meliou, will appear inVLDB 2016.

Shared Oblivious Storage
Nelly Fazio

We propose Shared Oblivious Storage (SOS), an extension of the oblivious storage (OS) model to the setting of group data sharing. In addition to providing server-side data-secrecy and access-pattern obliviousness guarantees as in traditional OS protocols, an SOS protocol allows arbitrary subsets of clients to share read/write access to cloud-stored data while preserving data-secrecy and access-pattern obliviousness guarantees with respect to unauthorized clients. To show the feasibility of SOS, we describe a provably secure generic construction based on the notions of outsider-anonymous broadcast encryption and multi-user oblivious RAM.
Joint work with Antonio Nicolosi and Milinda Perera.

Nondeterministic Separations

We survey recent research on the power of nondeterministic computation and how to use nondeterminism to get new separations of complexity classes. Results include separating NEXP from NP with limited advice, a new proof of the nondeterministic time hierarchy and a surprising relativized world

Non-Malleable Codes for Bounded Depth Circuits
Tal Malkin

We show how to construct efficient, unconditionally secure non-malleable codes for the class of functions with bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most O(n^0.25) bits, where n is the total number of bits in a codeword. Notably, this tampering class includes NC0.
This is joint work with Marshall Ball, Dana Dachman-Soled, and Mukul Kulkarni.

Graph Automorphism and Circuit Size
Eric Allender

The Minimum Circuit Size Problem is a well-studied example of a problem in NP that is believed to be intractable, but is not widely believed to be NP-complete. Until now, all reductions from of seemingly-hard problems to MCSP have made use of the [HILL] pseudorandom generator, which shows that any polynomial-time computable function can be inverted with relatively high probability by a probabilistic oracle machine with access to MCSP. This approach is not suitable for presenting a ZPP-reduction to MCSP from a problem that is not known to be in NP intersect coNP. Our main contribution is to present a very different reduction from Graph Isomorphism to MCSP; the reduction does not make use of [HILL]. (The reduction does require some new graph-theoreticl algorithms.) We use this to show that the Graph Automorphism problem is in ZPP relative to MCSP.
This is joint work with Josh Grochow and Cris Moore.

Efficient Money Burning in General Domains
Dimitris Tsipras

We study mechanism design where the payments charged to the agents are not in the form of monetary transfers, but are effectively burned. In this setting, the objective is to maximize social utility, i.e., the social welfare minus the payments charged. We consider a general setting with m discrete outcomes and n multidimensional agents. We present two essentially orthogonal randomized truthful mechanisms that extract an O(logm) fraction of the maximum welfare as social utility. Moreover, the first mechanism achieves a O(logm)-approximation for the social welfare, which is improved to an O(1)-approximation by the second mechanism. An interesting feature of the second mechanism is that it optimizes over an appropriately "smoothed" space, thus achieving smooth and efficient tradeoff between welfare approximation and the payments charged.
This is joint work with Dimitris Fotakis, Christos Tzamos, and Emmanouil Zampetakis.

A Control Dichotomy for Pure Scoring Rules
Lane A. Hemaspaandra

Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are "family-like'' is the recently introduced notion of (polynomial-time uniform) pure scoring rules, where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k ≤ 3, k-veto with k ≤ 2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a "hybrid" of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models f! or defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be "w.l.o.g." in fact do lose generality.
This is joint work with Edith Hemaspaandra and Henning Schnoor.