Satyen Kale

1 Microsoft Way
Redmond, WA 98052
(425) 707-0750 (office)
<firstname>.<lastname> microsoft [dot] com
http://www.cs.princeton.edu/~satyen/

EDUCATION

Princeton University	2007
Ph.D. in Computer Science. Advisor: Prof. Sanjeev Arora. Thesis topic: Efficient Algorithms using the Multiplicative Weights Update method
Indian Insitute of Technology, Bombay	2002
B.Tech. in Computer Science and Engineering. Advisor: Prof. Abhiram Ranade. Thesis topic: Spectral Algorithms for Data Representation and Manipulation.
Indian Statistical Insitute, Calcutta	Summers of 1999-2002
Participant in Nurture Program in Mathematics Completed equivalent of a Master's course in mathematics.

RESEARCH INTERESTS

My current research is the design of efficient algorithms for fundamental combinatorial optimization problems by approximately solving their linear or semidefinite programming relaxations, employing a variety of techniques from Machine Learning, Game Theory, and Convex Optimization. I am also interested in Spectral Algorithms and Complexity Theory. My research work includes efficient approximation algorithms for graph partitioning problems, matrix sparsification, online convex optimization, privacy-preserving algorithms, and streaming computation.

RESEARCH EXPERIENCE

Microsoft Research, Redmond, WA	Postdoctoral Researcher, 2007 - present
Working on sublinear time algorithms and learning theory.
Microsoft Research Silicon Valley Center, Mountain View, CA	Summer intern, 2006
Worked on privacy-preserving algorithms for releasing contingency tables, for learning, and for online optimization problems. Also, studied noise generation algorithms for preserving privacy.
IBM Almaden Research Center, San Jose, CA	Summer intern, 2005
Worked on streaming algorithms for probabilistic databases, efficient algorithms for computing correlated equilibria, and low distortion embeddings of the edit distance into L₁.
Cryptography Group, ETH Zürich, Switzerland	Summer intern, 2002
Developed sieve methods to find smooth numbers in short intervals.

HONORS

2^nd in the IIT Bombay class of 2002	2002
With a GPA of 9.85/10.00, placed second in a class of 420 students
All India rank 46 (out of about 150,000)	1998
Ranked 46 in the competitive Joint Entrance Examination to the Indian Institutes of Technology
Bronze medal in 37^th International Mathematics Olympiad	1997
Represented India at the IMO in Mar Del Plata, Argentina
Scholarship in National Talent Search Examination	1996
750 students are awarded scholarships every year all over India

PUBLICATIONS

Publications on Dissertation Topic:

Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria Elad Hazan and Satyen Kale. In 23^th International Conference on Neural Information Processing Systems (NIPS 2007).

A Combinatorial, Primal-Dual approach to Semidefinite Programs
Sanjeev Arora and Satyen Kale. In 39^th ACM Symposium on Theory of Computing (STOC 2007).

Logarithmic Regret Algorithms for Online Convex Optimization
Elad Hazan, Adam Kalai, Satyen Kale, and Amit Agarwal. In 19^th Annual Conference on Learning Theory (COLT 2006). Invited to appear in the Machine Learning Journal (MLJ) special issue for COLT 2006.

Algorithms for Portfolio Management based on the Newton Method
Amit Agarwal, Elad Hazan, Satyen Kale, and Robert Schapire. In 23^rd International Conference on Machine Learning (ICML 2006).

Fast Random Sampling Algorithm for Sparsifying Matrices
Sanjeev Arora, Elad Hazan, and Satyen Kale. In 10^th International Workshop on Randomization and Computation (RANDOM 2006).

Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method
Sanjeev Arora, Elad Hazan, and Satyen Kale. In 46^th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2005) (Gave talk at conference).

The Multiplicative Weights Update method: a Meta-Algorithm and some Applications
Sanjeev Arora, Elad Hazan, and Satyen Kale. Survey paper manuscript, 2005.

O(√log n) Approximation to SPARSEST CUT in Õ(n²) time
Sanjeev Arora, Elad Hazan, and Satyen Kale. In 45^th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2004) (Gave talk at conference).

Other Major Publications:

Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. In 26^th ACM Principles of Database Systems (PODS 2007).

Efficient Aggregation Algorithms for Probabilistic Data
T. S. Jayram, Satyen Kale, and Erik Vee. In 18^th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).

A Variation on SVD Based Image Compression
Abhiram Ranade, Srikanth S. M., and Satyen Kale. In 3^rd Workshop on Computer Vision, Graphics, and Image Processing (WCVGIP 2006).

Analysis and Algorithms for Content-based Event Matching
Satyen Kale, Elad Hazan, Fengyun Cao and Jaswinder Pal Singh. In 4^th International Workshop on Distributed Event-Based Systems (DEBS 2005).

Approximating Quadratic Programs with Positive Semidefiniteness Constraints
Elad Hazan and Satyen Kale. Princeton Tech Report TR-746-06, 2004.

INVITED TALKS

ISMP 2006, Rio de Janeiro, Brazil	August 2006
Invited talk on Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method
INFORMS 2005, San Francisco, CA	November 2005
Invited talk on Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method

Theory Seminar, Computer Science Department, Princeton, NJ	October 2004
Seminar talk on The Multiplicative Weights Update method
DIMACS Mixer Series, Rutgers University, NJ	September 2004
Workshop talk on O(√log n) Approximation to SPARSEST CUT in Õ(n²) time

TEACHING EXPERIENCE

Computer Science Department, Princeton University, Princeton, NJ	Fall 2005, 2006
Guest lecturer for COS 521: Advanced Algorithm Design Taught Machine Learning algorithms such as Perceptron, SVM, and the Multiplicative Weights algorithm, with applications.
Computer Science Department, Princeton University, Princeton, NJ	Fall 2004
Teaching Assistant for COS 226: Algorithms and Data Structures Conducted precepts and graded programming assignments, exercises, and examinations.
Computer Science Department, Princeton University, Princeton, NJ	Fall 2003
Teaching Assistant for COS 341: Discrete Mathematics Designed problem sets, conducted precepts, and graded homework assignments and examinations.

PROGRAMMING LANGUAGES

C, C++, Java, Matlab, Perl, Scheme.

REFERENCES

Will be provided on request.

Copy = Wrong. Design by Arnab Nandi.