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 about 3 years ago
To apply for Funding you must register by: September 05, 2011 over 3 years ago
Parent Program: Quantitative Geometry
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".

 


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 has preferred rates at the Rose Garden Inn, depending on room availability. 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 the MSRI rate on all room types available.

MSRI has preferred rates at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code 123MSRI. Our preferred rate is $139 per night for a Deluxe Queen/King, based on availability.

MSRI has preferred rates of $149 - $189 plus tax 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- Mathematical Science Research Inst. discount; or go to www.hotelshattuckplaza.com and click Book Now. Once on the reservation page, click “Promo/Corporate Code“ and input the code: msri.

MSRI has preferred rates of $110 - $140 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 “I am an individual traveler affiliated with MSRI”.

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

Show Directions to Venue

Show Visa/Immigration

Schedule
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
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
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
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
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
Dec 09, 2011
Friday
09:30 AM - 10:30 AM
  Information Theoretic Techniques in Theoretical Computer Science III
Oded Regev
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