Computer Science Colloquium
New York Area Theory Day
IBM/NYU/Columbia,
November 22, 2013
9:30AM
Warren Weaver Hall, 109
251 Mercer Street
New York, NY 10012
(Directions)
Fall 2013 Colloquia Calendar
Host
Courant Institute of Mathematical Sciences
External sponsorship by: Google
Synopsis
The New York Area Theory Day is a semiannual 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:3010:00: Coffee and bagels
10:0010:55: Prof. Noga Alon (Tel Aviv University and IAS)
Radio Networks
10:5511:05: Short break
11:0512:00: Prof. Adi Shamir (Weizmann Institute of Science and NYU)
Dissection: A New Paradigm for Solving Bicomposite Search Problems
12:0002:00: Lunch break (lunch not provided)
02:0002:55: Prof. Adam Marcus (Crisply, LLC and Yale University)
Bipartite Ramanujan Graphs of all degrees
02:5503:15: Coffee break
03:1504: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/theoryny
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 2lift 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 superpolynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, general polynomialsized linear programs are exactly as powerful as those arising from the SheraliAdams hierarchy.
Concrete consequences are that polynomialsized linear programming relaxation cannot achieve better than 1/2approximations for MAXCUT, 7/8approximations for MAX3SAT, or 3/4approximations for MAX2SAT.
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 SheraliAdams LP hierarchy, for approximating NPhard problems.
Joint work with Siu On Chan, James R. Lee, and Prasad Raghavendra.
=============================
"Every Day is Theory Day"
