Usual coordinates:
Friday, 2:00PM
Room 1314
Warren Weaver Hall
251 Mercer Street
Fall 2014 Schedule
Friday September 12
2:00AM
WWH 1314
Aravindan Vijayaraghavan (Courant) and Igor Shinkar (Courant)
Two short presentations
Aravindan Vijayaraghavan:
Title: Integrality of Stable Instances of Graph Partitioning problems
Abstract: We investigate the notion of stability that was proposed by Bilu and Linial
for studying practically interesting instances of graph partitioning and clustering problems.
Such instances have stable optimal solutions that do not change upon small perturbations of the
instance (multiplicative perturbations to the edge weights up to a factor of c). We obtain exact
polynomial-time algorithms for stable instances of Max Cut and Minimum Multiway cut.
We show that c-stable instances of Max-Cut can be solved efficiently, for c = O(\sqrt{log n} loglog n).
This represents a significant improvement over previous results, which needed the instances to be
c=O(\sqrt{n}) stable. We also give an algorithm for Multiway Cut instances that are 4-stable.
Our algorithms are based on a structural result showing that certain LP or SDP relaxations of
these problems become integral under sufficient stability.
Based on joint work with Konstantin Makarychev and Yury Makarychev
-----------------------
Igor Shinkar:
Title: Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Abstract:
We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that
for all even n there exists an explicit bijection f from the n-dimensional Boolean cube to the Hamming ball of equal volume
embedded in (n+1)-dimensional Boolean cube, such that for all x and y it holds that distance(x,y) / 5 <= distance(f(x),f(y))
<= 4 distance(x,y) , where distance(,) denotes the Hamming distance. In particular, this implies that the Hamming ball is
bi-Lipschitz transitive.
This result gives a strong negative answer to an open problem of Lovett and Viola (CC 2012), who raised the question in the
context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving
lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural
results of Boppana (IPL 97).
Joint work with Itai Benjamini and Gil Cohen.
Friday September 19
2:00PM
WWH 805
(Note the unusual location)
Pranjal Awasthi (Princeton)
Learning Halfspaces with Noise
Abstract: We study the problem of learning halfspaces in the malicious noise model of Valiant.
In this model, an adversary can corrupt an η fraction of both the label part and the feature
part of an example. We design a polynomial-time algorithm for learning halfspaces in R^d under
the uniform distribution with near optimal noise tolerance.
Our results also imply the first active learning algorithm for learning halfspaces that can handle malicious noise.
Joint work with Nina Balcan and Phil Long.
Friday September 26
2:00PM
WWH 1314
Omri Weinstein (Princeton)
Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis
Abstract: The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding *approximate* Nash equilibria efficiently, and is one of the major
open questions in algorithmic game theory.
We study the computational complexity of finding an \eps-approximate Nash equilibrium with good social
welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an epsilon-approximate
Nash equilibrium with good social welfare in a two player game and many variants of this problem is at
least as hard as finding a planted clique of size O(log n) in the random graph g(n,1/2).
We show that any polynomial time algorithm that finds an \eps-approximate Nash equilibrium with good
social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi. Specifically,
it would imply a 2^O(\sqrt{n}) algorithm for SAT.
Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving
the problem. Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games,
the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed
in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications.
Joint work with Mark Braverman and Young Kun Ko.
Thursday October 2
2:00PM
WWH 1314
(Note the unusual day)
Anindya De (Rutgers)
Central limit theorem for Gaussian chaos and deterministic counting for polynomial threshold functions
Abstract: It is a well-known fact that linear combinations of Gaussians are Gaussians.
What about polynomial combinations? In this talk, we will see a new central limit theorem
for polynomials of Gaussians. The techniques will draw from the so-called "Stein's method"
in probability theory and Malliavin calculus. As the main application, we will give the first
deterministic polynomial time algorithm for approximate counting of any constant degree PTF with
subconstant error. This theorem will involve a new decomposition procedure for polynomial which
might be of interest in other applications as well.
Joint work with Rocco Servedio.
Friday October 10
2:00PM
WWH 1314
Mark Braverman (Princeton)
TBA
Abstract: TBA
Friday October 17
2:00PM
WWH 805
(Note the unusual location)
Abstract: I will overview recent results on learning structured univariate
probability distributions. These results follow from a general approach to
density estimation based on piecewise polynomial approximations. The
key tool that enables this approach is a computationally efficient
algorithm for learning probability distributions that are well
approximated by piecewise polynomial density functions.
(Based in part on joint work with S. Chan, R. Servedio and X. Sun.)
Friday November 21
2:00PM
WWH 1314
Anand Louis (Princeton)
TBA
Abstract: TBA
Friday November 28
2:00PM
WWH 1314
Ran Raz (Weizmann)
Exponential Separation of Information and Communication
Abstract: TBA
Friday December 5
2:00PM
WWH 1314
Elliot Anshelevich (RPI)
Stable Matching, Friendship, and Altruism
Abstract: We will discuss both integral and fractional versions of "correlated stable matching"
problems. Each player is a node in a social network and strives to form a good match with a
neighboring player; the player utilities from forming a match are correlated. We consider
the existence, computation, and inefficiency of stable matchings from which no pair of players
wants to deviate. We especially focus on networks where players are embedded in a social context,
and may incorporate friendship relations or altruism into their decisions.
When the benefits from a match are the same for both players, we show that incorporating the
well-being of other players into their matching decisions significantly decreases the price of
stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching
achieving the price of stability bound always exists and can be reached in polynomial time. We
extend these results to more general matching rewards, when players matched to each other may
receive different utilities from the match. For this more general case, we show that incorporating
social context (i.e., "caring about your friends") can make an even larger difference, and greatly
reduce the price of anarchy. Finally, we extend most of our results to network contribution games,
in which players can decide how much effort to contribute to each incident edge, instead of simply
choosing a single node to match with.