Logo

Mathematical Sciences Research Institute

Home » Quantitative Geometry in Computer Science

Workshop

Quantitative Geometry in Computer Science December 05, 2011 - December 09, 2011
Registration Deadline: December 05, 2011 over 7 years ago
To apply for Funding you must register by: September 05, 2011 almost 8 years ago
Parent Program:
Organizers Irit Dinur (Weizmann Institute), Subhash Khot (Courant Institute), Manor Mendel* (Open University of Israel and Microsoft Research), Assaf Naor (Courant Institute), and Alistair Sinclair (University of California, Berkeley)
Speaker(s)

Show List of Speakers

Description
Geometric problems which are inherently quantitative occur in various aspects of theoretical computer science, including a)      Algorithmic tasks for geometric questions such as clustering and proximity data structures. b)      Geometric methods in the design of approximation algorithms for combinatorial optimization problems, including the analysis of semidefinite programs and embedding methods. c)       Geometric questions arising from computational complexity, particularly in hardness of approximation. These include isoperimetric and Fourier analytic problems. These include isoperimetric and Fourier analytic problems. This workshops aims to present recent progress in these directions. Bibliography (PDF)     Accommodation: A block of rooms has been reserved at the Rose Garden Inn. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show MSRI rate on all room types available. A block of rooms has been reserved at the Hotel Durant. Please mention MSRI and the workshop name when making reservations via phone, fax or e-mail. If you are making your reservations on line, please go to Hotel Durant website, choose your dates of stay and enter the "123MSRI" promo code in the box. The cut-off date for reservations is Midnight on the day of Tuesday, November 8, 2011. The rate is $110 per night plus tax. MSRI has a preferred rate of $135 at the Hotel Shattuck Plaza, depending on room availability. Guests can either call the hotel's main line at 510-845-7300 and ask for the MSRI rate; or go to Hotel Shattuck Plaza and enter dates of stay at top of screen and click Book Now.  Once on the reservation page, click Preferred/Corporate Rate Accounts and input the code "MSRI11".  
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Funding & Logistics Show All Collapse

Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

Show Lodging

MSRI does not hire an outside company to make hotel reservations for our workshop participants, or share the names and email addresses of our participants with an outside party. If you are contacted by a business that claims to represent MSRI and offers to book a hotel room for you, it is likely a scam. Please do not accept their services.

MSRI has preferred rates at the Hotel Shattuck Plaza, depending on room availability. Guests can call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Institute discount. To book online visit this page (the MSRI rate will automatically be applied).

MSRI has preferred rates at the Graduate Berkeley, depending on room availability. Reservations may be made by calling 510-845-8981. When making reservations, guests must request the MSRI preferred rate. Enter in the Promo Code MSRI123 (this code is not case sensitive).

MSRI has preferred rates at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select "Affiliated with the Space Sciences Lab, Lawrence Hall of Science or MSRI." When prompted for your UC Contact/Host, please list Chris Marshall (coord@msri.org).

MSRI has a preferred rates at Easton Hall and Gibbs Hall, depending on room availability. Guests can call the Reservations line at 510-204-0732 and ask for the MSRI- Mathematical Science Research Inst. rate. To book online visit this page, select "Request a Reservation" choose the dates you would like to stay and enter the code MSRI (this code is not case sensitive).

Additional lodging options may be found on our short term housing page.

Show Directions to Venue

Show Visa/Immigration

Schedule, Notes/Handouts & Videos
Show Schedule, Notes/Handouts & Videos
Show All Collapse
Dec 05, 2011
Monday
09:00 AM - 09:30 AM
  Welcome
09:30 AM - 10:30 AM
  Tutorial I - Nikhil Srivastava
10:30 AM - 11:00 AM
  Tea
11:00 AM - 12:00 PM
  Estimation of Small Norms in Data Streams
Jelani Nelson (Harvard University)
12:00 PM - 02:00 PM
  Lunch
02:00 PM - 03:00 PM
  Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs
Jonathan Kelner
03:00 PM - 03:30 PM
  Tea
03:30 PM - 04:20 PM
  Multi-Way Spectral Partitioning and Higher-Order Cheeger Inequalities
James Lee
Dec 06, 2011
Tuesday
09:30 AM - 10:30 AM
  Tutorial II - Nikhil Srivastava
10:30 AM - 11:00 AM
  Tea
11:00 AM - 12:00 PM
  A Nearly Optimal Solution for the Chow Parameters Problem and Applications
Ilias Diakonikolas
12:00 PM - 02:00 PM
  Lunch
02:00 PM - 03:00 PM
  Recent Developments in Learning Convex Sets
Adam Klivans
03:00 PM - 03:30 PM
  Tea
03:30 PM - 04:30 PM
  Gaussian Noise Sensitivity
Ryan O'Donnell (Carnegie Mellon University)
04:30 PM - 06:30 PM
  Welcome Reception
Dec 07, 2011
Wednesday
09:30 AM - 10:20 AM
  Tutorial III - Nikhil Srivastava
10:20 AM - 10:50 AM
  Tea
10:50 AM - 11:40 AM
  Information Theoretic Techniques in Theoretical Computer Science I
Oded Regev (New York University, Courant Institute)
11:40 AM - 12:40 PM
  Incidence Geometry and Applications in Theoretical Computer Science
Shubhangi Saraf
12:40 PM - 02:40 PM
  Lunch
Dec 08, 2011
Thursday
09:30 AM - 10:20 AM
  Information Theoretic Techniques in Theoretical Computer Science II
Oded Regev (New York University, Courant Institute)
10:20 AM - 10:50 AM
  Tea
10:50 AM - 11:45 AM
  Nearest Neighbor Search and Metric Expansion
Kunal Talwar
11:45 AM - 12:45 PM
  A New Infinity of Distance Oracles for Sparse Graphs
Mihai Patrascu
12:45 PM - 02:30 PM
  Lunch
02:30 PM - 03:30 PM
  A Deterministic Algorithm for Matrix Completion - Adi Shraibman
03:30 PM - 04:00 PM
  Tea
04:00 PM - 04:50 PM
  Algorithmic Applications of M-Ellipsoids
Santosh Vempala (Georgia Institute of Technology)
Dec 09, 2011
Friday
09:30 AM - 10:30 AM
  Information Theoretic Techniques in Theoretical Computer Science III
Oded Regev (New York University, Courant Institute)
10:30 AM - 11:00 AM
  Tea
11:00 AM - 12:00 PM
  Tight Bounds for Distributed Functional Monitoring - David Woodruff
12:00 PM - 01:00 PM
  Remarks on Coresets for Minimum Enclosing Ellipsoids - Ken Clarkson
01:00 PM - 03:00 PM
  Lunch