Midwest Theory Day

The 66th Midwest Theory Day will take place at
The University of Michigan on Saturday, December 6, 2014.

UofM Beyster Building

[Overview] [Registration] [Schedule] [Invited Talks] [Organizers]


We are inviting anyone interested in theoretical computer science to attend the Fall edition of the Midwest Theory Day at The University of Michigan, on December 6, 2014. The event is a semiannual tradition among the CS theorists in the Midwest, aiming to be an opportunity for us to meet each other, share our research, and initiate collaborations. Please find out more about previous MTDs.

Like us on Facebook! (Also discuss carpooling, evening plans, etc.)


Registration is free, but you must register to participate. We will provide break snacks and lunch. To attend, click below. You can enter a title and abstract or register as a non-speaking attendee.

Sign me up!

Schedule (subject to change)

10:00-10:55 Arrivals1670 BBB Coffee and Registration
10:55-11:00 Welcome Remarks1670 BBB Martin Strauss
11:00-12:00 Talks 1670 BBB Ilya Volkovich Characterizing Arithmetic Read-Once Formulae
Steven Damelin Allignment in $R^D$
3725 BBB Wei-Hsuan Yu New upper bounds for spherical two-distance sets from semidefinite programming
Tyson Williams Siegel's theorem, edge coloring, and a holant dichotomy
12:00-1:30 Lunch1670 BBB Provided
1:30-2:00 Talks 1670 BBB David Woodruff Principal Component Analysis and Higher Correlations for Distributed Data
3725 BBB Brendan Juba Conditional Distribution Search
2:00-3:00 Invited Speaker1670 BBB David Steurer Lower bounds on the size of semidefinite programming relaxations
3:00-4:00 Break1670 BBB Coffee and Snacks
4:00-5:00 Talks 1670 BBB Eric Blais The information complexity of Hamming distance
Abhiram Natarajan Computational Complexity of Certifying the Restricted Isometry Property
3725 BBB Harold Connamacher The 2+p Question in Random Constraint Satisfaction Problems
Heng Guo The Complexity of Ising Models with Complex Weights
5:00-5:30 TBD: Bonus talk, rump session, etc.
5:30-5:31 Closing Remarks 1670 BBBMartin Strauss

Invited Talk

David Steurer

Speaker: David Steurer, Cornell University.

Title: Lower bounds on the size of semidefinite programming relaxations

Abstract: We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^{\delta}}$, for some constant $\delta > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit polytope. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX 3-SAT. Joint work with James Lee and Prasad Raghavendra.

Bio: David Steurer is an Assistant Professor at Cornell University. He investigates the power and limitations of efficient algorithms for optimization problems. A focus of his work has been semidefinite programming--the systematic combination of linear programming and spectral methods--which for a wide range of problems gives the best known and potentially optimal guarantees in terms of approximation quality. Steurer received his PhD from Princeton University and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University. He is the recipient of the 2010 FOCS best paper award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, and a Microsoft Research Faculty Fellowship.

Local Information

The event will take place at the home of the Computer Science and Engineering Division, the

Beyster Building, BBB
2260 Hayward Street
Ann Arbor, MI 48109.

This is on "North Campus." Wayfinders should note that Michigan also has a larger "Central Campus" and other smaller campuses. (Note: previously the venue was announced as EECS 1200, which is nearby. Signs and people will direct you from EECS to BBB, if necessary.)

Parking: Parking is free on weekends. The closest lot is NC48.
Accomodations: The closest hotels are about two miles away. There are city buses and campus buses between campus and hotels. Please email the organizer for help.


Anna C. Gilbert, Martin J. Strauss, and Ilya Volkovich. Contact martinjs at the server umich.edu.