Shripad Thite

Computer scientist, researcher in algorithms in computational geometry and algorithms in applied areas, including scientific computing, graphics and visualization, wireless networking, robotics, microeconomic simulation, and market design.

Shripad Thite’s Specialties:

Developing geometric algorithms and using geometric insight to exploit previously unknown connections between problems in diverse areas including theory and practical applications.

Shripad Thite’s Experience

Software Engineer

Google

(Public Company; GOOG; Internet industry)

October 2009 — Present (2 months)
Postdoctoral Fellow

California Institute of Technology

(Educational Institution; Research industry)

September 2007 — August 2009 (2 years )

* Conduct research in algorithms for combinatorial problems in computational geometry and topology as a scholar in the Center for the Mathematics of Information, Information Science & Technology.
* Collaborate with Caltech researchers in Computer Science on problems in computational geometry and topology, such as those motivated by graphics applications.
* Investigate algorithms for robust clustering and regression of interval data, with Caltech colleagues.
* Research algorithmic problems in topology such as computing optimum homotopy between curves on surfaces and homeomorphism between surfaces, and curve and surface approximation.
* Researching algorithms for design and implementation of a real-time spot auction market for online display advertising, including algorithms for price support in multiple online Vickrey auctions and for inventory matching to maximize return-on-investment.
* Teaching special topics course in Computer Science: Algorithms in Geometry and Topology.
Postdoctoral Researcher

Eindhoven University of Technology

(Educational Institution; Research industry)

September 2005 — August 2007 (2 years )

* Devised external-memory cache-efficient and cache-oblivious algorithms for fundamental problems in computational geometry and in optimization. Results are applicable in Geographic Information Systems, where map data is too massive to fit entirely in main memory; Algorithms are practical and implementable as well as theoretically efficient.
* Designed a cache-oblivious IO-efficient version of the algorithm of Frederickson and Johnson for selecting in sorted X+Y matrices. The matrix selection algorithm is a key building block of many other optimization algorithms, sometimes serving as an alternative to expensive parametric search.
* Proved bounds on the combinatorial complexity of Voronoi diagrams on realistic terrains—studied problems in combinatorial geometry.
Research Assistant

University of Illinois at Urbana-Champaign

(Educational Institution; 10,001 or more employees; Higher Education industry)

August 1999 — September 2005 (6 years 2 months)

• Developed algorithms for spacetime meshing to support novel spacetime-discontinuous Galerkin finite element methods. Our algorithms were the first adaptive geometric algorithms to construct efficiently solvable spacetime meshes. The meshes we construct are suitable for efficient simulation of time-dependent wave-like physical phenomena using spacetime discontinuous Galerkin finite element methods.
• Designed algorithms for problems in computational topology, such as the homotopic Fréchet distance between curves and shortest pants decompositions of surfaces.
• Studied motion planning and grasping problems in robotics and designed an algorithm for capturing an object in the plane with three robots.
• Developed algorithms for computing a minimum-cost binary search tree or BST on a hierarchical memory model of computation, suitable for constructing such a data structure for massive data that is stored across multiple levels of memory devices with vastly different access times.
Graduate Research Assistant

Los Alamos National Laboratory

(Government Agency; 10,001 or more employees; Research industry)

May 2002 — August 2002 (4 months)

• Intern in the Basic & Applied Simulation Science (D-2) group at LANL.
• Developed software tools for simulating the economics of large-scale auction-based deregulated markets for electrical power. Designed and implemented an agent-based, microeconomic, scalable model for the simulation of a deregulated electrical power market. The project included writing computer software to simulate power demand and consumption, market forces such as monopolistic and oligopolistic behavior, external regulatory policies, and physical constraints of the power grid. Unique features our simulator were individual, demographics-based elastic demand profiles; configurable matching between buyers and sellers; and flexible market clearing mechanisms. Evaluated the performance and efficiency of the market under different market clearing algorithms and sellers’ strategies.
Graduate Research Assistant

Los Alamos National Laboratory

(Government Agency; 10,001 or more employees; Research industry)

May 2001 — August 2001 (4 months)

• Intern in the Basic & Applied Simulation Science (D-2) group at LANL.
• Designed algorithms for conflict-free communication in ad-hoc wireless networks and proved bounds on the maximum throughput of such networks. Conducted research on theoretical and practical problems associated with wireless radio networks. This work intersects the areas of graph theory, computational geometry, and networking. Algorithms for distance-2 edge coloring and matching in graphs modeling ad-hoc wireless networks can be applied to designing routing protocols for such networks and for predicting the network throughput.
Teaching Assistant

University of Illinois at Urbana-Champaign

(Educational Institution; 10,001 or more employees; Higher Education industry)

August 1997 — May 1999 (1 year 10 months)

Instructor: C and C++ Programming Laboratories (2 semesters)

Teaching Assistant: Introduction to the Theory of Computation; Combinatorial Algorithms; Automata, Formal Languages, and Computational Complexity (3 semesters)
Graduate Research Assistant

Los Alamos National Laboratory

(Government Agency; 10,001 or more employees; Research industry)

May 1998 — August 1998 (4 months)

• Optimized numerical software libraries for external-memory computation to improve cache performance: extended blocking algorithms for matrices to improve memory-efficiency of matrix operations. Implemented and simulated the same on an SGI Origin multiprocessor system, and empirically demonstrated a significant improvement in performance.
• Implemented a blocking algorithm for graphs, as proposed by Awerbuch et al., and investigated its performance.

Shripad Thite’s Education

University of Illinois at Urbana-Champaign

Ph.D. , Computer Science , 1997 — 2005

Thesis: "Spacetime Meshing for Discontinuous Galerkin Methods"
Advisor: Prof. Jeff Erickson
University of Illinois at Urbana-Champaign

M.S. , Computer Science , 1997 — 2001

Thesis: "Optimum Binary Search Trees on the Hierarchical Memory Model"
Advisor: Prof. Michael Loui
College of Engineering Pune

B.E. , Computer Engineering , 1993 — 1997

D.Y. Patil Gold Medal from University of Pune
Sir Parshurambhau College

Science/Electronics 1991 — 1993
Abhinav Vidyalay

1978 — 1991