Stanford Theory Seminar

Claude E. Shannon's 100th Birthday

Topic: 
Centennial year of the 'Father of the Information Age'
Abstract / Description: 

From UCLA Shannon Centennial Celebration website:

Claude Shannon was an American mathematician, electrical engineer, and cryptographer known as "the father of information theory". Shannon founded information theory and is perhaps equally well known for founding both digital computer and digital circuit design theory. Shannon also laid the foundations of cryptography and did basic work on code breaking and secure telecommunications.

 

Events taking place around the world are listed at IEEE Information Theory Society.

Date and Time: 
Saturday, April 30, 2016 - 12:00pm
Venue: 
N/A

Stanford Theory Seminar

Topic: 
TBA
Abstract / Description: 

Theory Lunch

Stanford Theory Seminar is the newly revived version of Stanford Algorithms Seminar/AFLB. The seminar is usually held in Gates 498 or Theory Lounge(Gates 463A).

If you would like to give a talk, or if you have any questions, please send an email to the coordinators Gregory Valiant and Huacheng Yu.

Date and Time: 
Thursday, December 10, 2015 - 12:15pm to 1:00pm
Venue: 
Gates 498 or Gates 463A

Stanford Theory Seminar

Topic: 
TBA
Abstract / Description: 

Theory Lunch

Stanford Theory Seminar is the newly revived version of Stanford Algorithms Seminar/AFLB. The seminar is usually held in Gates 498 or Theory Lounge(Gates 463A).

If you would like to give a talk, or if you have any questions, please send an email to the coordinators Gregory Valiant and Huacheng Yu.

Date and Time: 
Thursday, December 3, 2015 - 12:15pm to 1:00pm
Venue: 
Gates 498 or Gates 463A

Stanford Theory Seminar

Topic: 
TBA
Abstract / Description: 

Theory Lunch

Stanford Theory Seminar is the newly revived version of Stanford Algorithms Seminar/AFLB. The seminar is usually held in Gates 498 or Theory Lounge(Gates 463A).

If you would like to give a talk, or if you have any questions, please send an email to the coordinators Gregory Valiant and Huacheng Yu.

Date and Time: 
Thursday, November 19, 2015 - 12:15pm to 1:00pm
Venue: 
Gates 498 or Gates 463A

Stanford Theory Seminar

Topic: 
TBA
Abstract / Description: 

Theory Lunch

Stanford Theory Seminar is the newly revived version of Stanford Algorithms Seminar/AFLB. The seminar is usually held in Gates 498 or Theory Lounge(Gates 463A).

If you would like to give a talk, or if you have any questions, please send an email to the coordinators Gregory Valiant and Huacheng Yu.

Date and Time: 
Thursday, November 12, 2015 - 12:15pm to 1:00pm
Venue: 
Gates 463A

Stanford Theory Seminar

Topic: 
Euclidean k-means: an SDP relaxation and hardness of approximation
Abstract / Description: 

The Euclidean k-means problem is a classical problem that has been extensively studied in several communities. In this problem, we are given a set of n points in Euclidean space R^d , and the goal is to choose k center points in R^d so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general k and a (1+eps)-approximation which runs in time poly(n).exp(k/eps). At the other extreme, the only known computational complexity result for this problem is NP-hardness. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in R^d can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all k, d.

In this talk, I will present a new SDP relaxation for k-means. The study of integrality gaps for this relaxation led to the first hardness of approximation result for the Euclidean k-means problem. We show that there exists a constant delta > 0 such that it is NP-hard to approximate the k-means objective to within a factor of (1+delta). I will outline some of the ideas in the hardness of approximation proof, and discuss other research directions that came from the study of the k-means SDP.

Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy and Ali Sinop.

Date and Time: 
Thursday, September 24, 2015 - 4:15pm to 5:15pm
Venue: 
Gates 463A
Subscribe to RSS - Stanford Theory Seminar