NYCAC 2014 - Abstracts

Friday, November 14, 2014,   New York City
The Graduate Center, CUNY
Room 4102 (Science Center) and room 4421

The New York Colloquium on Algorithms and Complexity

Xi Chen

On the Complexity of Nash Equilibria in Anonymous Games
Anonymous games are a large and well-studied class of succinct multiplayer games, in which the payoff of each player depends only on her own strategy and number of other players playing each strategy. In a sequence of papers, Daskalakis and Papadimitriou studied the problem of finding an approximate Nash equilibrium in an anonymous game, and obtained polynomial-time approximation schemes when the number of strategies is bounded. In this talk we briefly review their results and show that the problem is complete in PPAD when the number of strategies is at least seven and the approximation parameter is exponentially small, confirming a conjecture of Daskalakis and Papadimitriou.
Joint work with David Durfee (Georgia Institute of Technology) and Anthi Orfanou (Columbia University).

Lane Hemaspaandra

Control in the Presence of Manipulators: Cooperative and Competitive Cases
Control and manipulation are two of the most studied types of attacks on elections. We study the complexity of control attacks on elections in which there are manipulators. We study both the case where the "chair" who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet for a Borda-voting case we show that such clashes raise the complexity unless NP=coNP. This is joint work with Zack Fitzsimmons and Edith Hemaspaandra.

Alan Selman

Disjoint NP-pairs and Propositional Proof Systems
This talk surveys results on disjoint NP-pairs, propositional proof systems, function classes, and promise classes---including results that demonstrate close connections that bind these topics together. We illustrate important links between the questions of whether these classes have complete objects and whether optimal proof systems may exist.

Daniel Stefankovic

Spin models: connections between complexity, phase transition, belief propagation, and induced matrix norms
What are the typical configurations of a spin model (for example, Ising model, or Potts model) on a random regular graph ? We show that the answer to this question is characterized by tree recursions (belief propagation) and p->q operator matrix norms.
Understanding the typical configurations allows us to show hardness of approximating the partition function for certain multispin models (for example, Potts model) on d-regular graphs in the non-uniqueness regime (that is, when the Gibbs measure on infinite d-regular tree is not unique). Joint work with Andreas Galainis, and Eric Vigoda.

Rocco Servedio

A Probably Approximately Correct Lower Bound for Non-Adaptive Boolean Function Monotonicity Testing
Boolean function monotonicity testing is a problem that has received a lot of attention in the property testing community. In a recent work (FOCS 2014) Chen, Servedio and Tan gave an $\tilde{\Omega}(n^{1/5})$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown $n$-variable Boolean function is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $\Omega(\log n)$ for this model due to Fischer et al from 2002. More recently, Chen, De, Servedio and Tan extended this lower bound to $\Omega(n^{1/2-\tau})$ for any $\tau>0$. If one believes (as is commonly conjectured) that the true nonadaptive query complexity of monotonicity testing is $\Theta(\sqrt{n})$, this new lower bound is probably approximately correct (or more precisely, probably approximately tight).
In this talk I will present the main ideas behind these recent results and talk about directions for future work on the monotonicity testing problem.

Moti Yung

Surveillance Adversary Protocols: past and future

Manolis Zampetakis

Mechanism Design in presence of Verification and Applications
The basic mechanism design model assumes that each agent can follow any of its strategies, independently of its type. Thus the mechanism cannot use any ”real-world” information about the agents. This is the norm in mechanism design and it models well the negotiation stage in which agents do nothing but communicate. A simple type of modification to the model suggests itself: a problem definition may limit the set of strategies available to each agent as a function of its type. In this work we investigate the way mechanism design changes under the assumption of verification.
The first deference in the mechanism design with verification is the existence of non- truthful implementations of social choice functions. We present the reason why this way of implementation is not really helpful in the solution concept of dominant strategy equi- librium and we present a way it could be useful using the concept of Nash equilibrium. In this work, we also investigate the reasons that make symmetric partial verification essentially useless in virtually all domains. Departing from previous work, we consider any possible (finite or infinite) domain and general symmetric verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints, and prove that this property is sufficient for the equivalence of truthfulness and M -truthfulness. Since the simplest symmetric verification is the local verification, specific cases of our result are closely related, in the case without money, to the research about the equivalence of local truthfulness and global truthfulness.