# NYCAC 2014 - Abstracts

Friday, November 14, 2014,   New York City
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