Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Warren Weaver Hall 109
Date: November 22, 2013, 9:30 a.m.
Host: Courant Institute of Mathematical Sciences
Synopsis:
The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York Metropolitan area for one day of interaction and discussion. The meeting is free and open to everyone;
in particular, students are encouraged to attend.
======= Program =======
9:30--10:00: Coffee and bagels
10:00--10:55: Prof. Noga Alon (Tel Aviv University and IAS) Radio Networks
10:55--11:05: Short break
11:05--12:00: Prof. Adi Shamir (Weizmann Institute of Science and NYU) Dissection: A New Paradigm for Solving Bicomposite Search Problems
12:00--02:00: Lunch break (lunch not provided)
02:00--02:55: Prof. Adam Marcus (Crisply, LLC and Yale University) Bipartite Ramanujan Graphs of all degrees
02:55--03:15: Coffee break
03:15--04:10: Prof. David Steurer (Cornell University) Approximate Constraint Satisfaction Requires Large LP Relaxations
For directions, please see http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny
Organizers:
Yevgeniy Dodis: dodis@cs.nyu.edu Tal Rabin: talr@us.ibm.com Cliff Stein: cliff@ieor.columbia.edu
======== Abstracts ========
Radio Networks Prof. Noga Alon (Tel Aviv University and IAS)
Abstract: The radio network model is a standard theoretical model for studying wireless comnmunication. In this model communication happens in synchronous rounds in which each node can either send a packet or listen. Only listening nodes for which exactly one neighbor sends receive a packet. The study of this model leads to intriguing combinatorial, algorithmic and graph theoretic questions. I will describe several recent results in this topic including the efficient design of shared radio networks (in joint work with Moitra and Sudakov), and the investigation of the broadcast problem in this model (in joint work with Ghaffari, Haeupler and Khabbazian).
=============================
Dissection: A New Paradigm for Solving Bicomposite Search Problems Prof. Adi Shamir (Weizmann Institute of Science and NYU)
Abstract: Most combinatorial search problems can be described by a collection of possible states, a list of possible actions which map each current state into some next state, and a pair of initial and final states. The problem is to find a sequence of actions which map the given initial state into the desired final state. One can always solve such problems by trying out all the possible sequences of actions, but in many cases it is possible to exploit special properties of the states and actions in order to lower the exponential complexity of exhaustive search. In this talk I will introduce the new notion of bicomposite search problems, whose solution can be partitioned both along the action and the state dimensions, and show that such problems can be solved with a new algorithmic paradigm which we call dissection with greatly reduced com- binations of time and space complexities. To demonstrate the wide applicability of these ideas, I will show how to improve the best known algorithms for untangling Rubik's cube, for solving various set partition problems, and for breaking multiple encryption schemes.
Joint work with Itai Dinur, Orr Dunkelman, and Nathan Keller.
=============================
Bipartite Ramanujan Graphs of all degrees Prof. Adam Marcus (Crisply, LLC and Yale University)
Abstract: We will outline the proof that shows the existence of bipartite Ramanujan Graphs of any degree as well as some of mixed degrees. Our approach uses the idea of Bilu and Linial to show that there exists a 2-lift of a given Ramanujan graph which maintains the Ramanujan property. This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials."
This talk is intended to be accessible by a general computer science audience, and represents joint work with Dan Spielman and Nikhil Srivastava.
=============================
Approximate Constraint Satisfaction Requires Large LP Relaxations Prof. David Steurer (Cornell University)
Abstract: We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, general polynomial-sized linear programs are exactly as powerful as those arising from the Sherali-Adams hierarchy.
Concrete consequences are that polynomial-sized linear programming relaxation cannot achieve better than 1/2-approximations for MAX-CUT, 7/8-approximations for MAX-3SAT, or 3/4-approximations for MAX-2SAT.
Our techniques bring together two formerly disparate lines of research. On the one hand, there has been a recent sequence of exciting lower bounds on the size of extended formulations for various polytopes that arise in combinatorial optimization. At the same time, researchers have extensively studied the power of specific hierarchies, such as the Sherali-Adams LP hierarchy, for approximating NP-hard problems.
Joint work with Siu On Chan, James R. Lee, and Prasad Raghavendra.
=============================
"Every Day is Theory Day"
Notes:
In-person attendance only available to those with active NYU ID cards.