|
|
Download PDF
Chinmay D. Karande
Google Inc.
|
1600 Amphitheatre Pkwy
Mountain View CA 94043
[first initial][last name][at][gmail][dot][com]
|
| EDUCATION
|
- Ph.D. in Algorithms, Combinatorics and Optimization
- College of Computing, Georgia Institute of Technology, Atlanta
- B.Tech. in Computer Science and Engineering
- Dept. of Computer Science and Engineering, Indian Institute of Technology, Bombay
|
|
|
|
PUBLICATIONS
|
- Online Bipartite Matching with Unknown Distributions
- Co-authors: Aranyak Mehta and Pushkar Tripathi.
To appear at the 43rd ACM Symposium on Theory of Computing, to be held in San Jose, CA in June 2011.
- Online Vertex-weighted Bipartite Matching and Single-bid Budgeted Allocations PDF
- Co-authors: Gagan Aggarwal, Gagan Goel and Aranyak Mehta.
In proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, held in San Francisco, CA in January 2011.
- Market Equilibrium with Transaction Costs PDF
- Co-authors: Nikhil Devanur and Sourav Chakraborty.
In proceedings of the 6th International Workshop on Internet and Network Economics, held in Stanford, CA in December 2010.
- Single-Parameter Combinatorial Auctions with Partially Public Valuations PDF
- Co-authors: Gagan Goel and Lei Wang.
In proceedings of the 3rd International Symposium on Algorithmic Game Theory, held in Athens, Greece in October 2010.
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions PDF
- Co-authors: Gagan Goel, Pushkar Tripathi and Lei Wang.
In proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, held in Atlanta, GA in October 2009.
- Speeding up Algorithms on Compressed Webgraphs PDF
- Co-authors: Kumar Chellapilla and Reid Andersen.
In proceedings of the 2nd ACM International Conference on Web Search and Data Mining, held in Barcelona, Spain in February 2009.
Journal version to appear in a special issue of Internet Mathematics.
- A Note on the Problem of Reporting Maximal Cliques URL
- Co-author: Frederic Cazals.
Theoretical Computer Science - Volume 407:564-568, Nov. 2008.
- Computing Market Equilibrium: Beyond Weak Gross Substitutes PDF
- Co-author: Nikhil Devanur.
In proceedings of the 3rd Workshop on Internet and Network Economics, held in San Diego, CA in December 2007.
- An Algorithm for Reporting Maximal C-Cliques URL
- Co-author: Frederic Cazals.
Theoretical Computer Science - Volume 349, Issue 3:484-490, Dec 2005.
- The Effect of Malice on Social Optimum in Congestion Games URL
- Manuscript. Feb 2008.
- Polynomially Correlated Knapsack is NP-Complete URL
- Manuscript. July 2007.
- Non-preemptive Precedence Constraint Scheduling
- Senior Thesis at IIT Bombay, May 2006.
- NP-completeness of Flow Shop Scheduling
- Junior Thesis at IIT Bombay, May 2005.
|
|
|
PATENTS
|
- Speeding Up Analysis of Compressed Web Graphs
- Patent pending (Microsoft Corporation, May 2009)
- Short Paths in Web Graphs with Small Query Time
- Patent pending (Microsoft Corporation, May 2009)
|
|
|
INVITED TALKS
|
- Submodularity in Combinatorial Optimization and Mechanism Design
- At the SIAM Conference on Discrete Mathematics held in Austin, TX in June 2010.
- Market Equilibrium with Transaction Costs
- At the Institute for Operations Research and Management Sciences Annual Meeting held in San Diego, CA in October 2009.
|
|
|
SELECTED DEVELOPMENT PROJECTS
|
- An Exploratory Tool for Multi-structured Data
- At Google Research, Mountain View in Spring 2010.
- Finding Short Paths in Web Graphs with Small Query Time
- At Microsoft, Redmond with the Live Labs team in Summer 2008.
- A Classifier for Spam Targetting Misspelled Queries
- At Microsoft, Redmond with the Search Relevance team in Summer 2007.
| |
| ACADEMIC ACHIEVEMENTS |
- ACM International Collegiate Programming Competition
- Part of IIT Bombay and Georgia Tech teams attending the ACM ICPC world finals in 2006 and 2008 respectively.
- Outstanding Graduate Teaching Assistant Award
- College of Computing, Georgia Institute of Technology, April 2010.
- Aditya Birla Scholarship
- Scholarship holder 2002-2006.
- Indian Institute of Technology Joint Entrance Examination
- Ranked 33rd nationally.
- Indian National Physics Olympiad 2002 (INPhO)
- Among 30 Gold Medalists from all over India.
- Indian National Chemistry Olympiad 2002 (INChO)
- Among 30 Gold Medalists from all over India.
|
|
|
