summary of site-wide JavaScript functionality United States-English
» Contact HP
 Search: HP Labs All of HP US

# Vinay Deolalikar

Principal Research Scientist, HP Labs

printable version
»

## HP Labs

 » Research
 » News and events » Technical reports
 » About HP Labs » Careers @ HP Labs » People » Worldwide sites

Contents:

Research Interests / Selected Publications / Math Lectures Notes / Brief Bio

Research Interests

I am a mathematician working at HP Labs. My work is a mix of  basic research and applied industrial research.  My current project at HP deals with algorithms for information management using techniques from machine learning and data mining.  My areas of interest are the following:

• Number theory and algebraic geometry, with applications to coding theory
• Machine learning and data mining, with applications to information management
• Mathematical logic and its role in theoretical computer science
• Stochastic processes with applications to modeling and randomized algorithms
• Statistics with applications to database estimation algorithms
• Digital communications, with applications to wireless communication

### Selected Publications

My research can be broadly divided into basic and industrial.

BASIC RESEARCH

Vinay Deolalikar. P ≠ NP.  The preliminary version was meant to solicit feedback from a few researchers as is customarily done. It illustrated the interplay of principles from various areas, which was the major effort in constructing the proof. I have fixed all the issues that were raised about the preliminary version in a revised manuscript; clarified some concepts; and obtained simpler proofs of several claims.  Once I hear back from the journal as part of due process, I will put up the final version on this website.

Deolalikar, Vinay. Ring theoretic study of linear codes using additive polynomials. Finite fields and applications, 91--102, Contemp. Math., 461, Amer. Math. Soc., Providence, RI, 2008. MR2436327 (2010a:94108)

Deolalikar, Vinay; Hamkins, Joel David; Schindler, Ralf. ${\rm P}\neq{\rm NP}\cap$ co-NP for infinite time Turing machines. J. Logic Comput. 15 (2005), no. 5, 577--592. MR2172411 (2006k:68026)

Deolalikar, Vinay. Explicitly constructed extensions of the rational function field with prescribed splitting. Finite Fields Appl. 9 (2003), no. 2, 222--236. MR1968032 (2004c:11215)

Deolalikar, Vinay. Determining irreducibility and ramification groups for an additive extension of the rational function field. J. Number Theory 97 (2002), no. 2, 269--286. MR1942960 (2004d:11114)

Deolalikar, Vinay. Extensions of algebraic function fields with complete splitting of all rational places. Comm. Algebra 30 (2002), no. 6, 2687--2698. MR1908233 (2003f:14019)

Aleshnikov, Ilia; Deolalikar, Vinay; Kumar, P. Vijay; Stichtenoth, Henning. Towards a basis for the space of regular functions in a tower of function fields meeting the Drinfel'd-Vladut bound. Finite fields and applications, Springer, Berlin, 2001. (Outstanding Research Paper Award: USC Electrical Engineering-Systems, 2000).

INDUSTRIAL RESEARCH
I have worked on several projects that require analysis of mathematical models for various systems.

Lillibridge, Mark; Eshghi, Kave; Bhagwat, Deepavali; Deolalikar, Vinay; Trezis, Greg; Gamble, Peter. Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality. FAST 2009. pp.111--123

Deolalikar, Vinay; Laffitte, Hernan. Provenance as data mining: combining file system metadata with content analysis." Theory and applications of Provenance 2009.

Deolalikar, Vinay; Choudur, Lakshminarayan; Laffitte, Hernan. A new composite estimator of distinct values that performs well in a wide range of skewness." HP Labs Technical report 2008.

Deolalikar, Vinay, Eshghi, Kave; Laffitte, Hernan. A lightweight distributed algorithm based on order statistics to answer top-k queries." HP Labs Technical report 2007.

Deolalikar, Vinay. Timed Markov models and their Laplace transforms, with applications to reliability models." HP Labs Technical report 2006.

Mathematics Lectures  (Stanford University) and Notes

Notes from some lectures I have given in the broad areas of Algebraic Geometry and Number Theory at Stanford Mathematics:

• Modular Forms and Modular Curves (3 lectures, 2000-2001)

• Moduli Spaces of Curves and Teichmuller theory (4 lectures, 2004)
• Lecture 1: Low genus (0 and 1), construction of M_1
• Lecture 2: Orbifolds, Teichmuller space, Mapping class groups, Fenchel Nielsen coordinates
• Lecture 3: Divisors, Line bundles, and Chern classes,
• Lecture 4: Algebraic cycles, Chow Groups, Hodge Theory (intro)

• Hodge Theory (3 lectures, 2004)
• Lecture 1: Hodge theory on Riemann manifolds, de Rham theorem, Laplace Beltrami, Harmonic forms, Dolbeault, Bott Chern cohomology
• Lecture 2: Hodge theory on Hermitian manifolds and Kahler manifolds, Hard Lifschitz, Weak Lifschitz
• Lecture 3: Mixed Hodge structures, Leray Spectral sequence, semi-simplicity, Lifschitz decomposition

Self-study notes on some areas in Logic:

• Elementary Equivalence, Partial Isomorphism, and Scott-Karp analysis (self-study notes)

### Brief Bio

Born in 1971 in New Delhi, India.   Married with two children.  Other interests include historical and religious aspects of Hindu Dharma.  Indian citizen.

Education

Ph.D. (Electrical Engineering, jointly with Mathematics) University of Southern California, May 1999.  Thesis: On splitting places of degree one in extensions of algebraic function fields, towers of function fields meeting asymptotic bounds, and basis constructions for algebraic-geometric codes)

Masters in Electrical Engineering (5-year) Indian Institute of Technology, Bombay, July 1994.  Dissertation: New approaches to learning and classification in feedforward neural networks

You can reach me at:

E-mail: first.last (at) hp (dot) com
FAX: (650) 852-3791

Bldg 1U, Hewlett Packard Labs