Saugata Basu

Professor

Purdue University

Contact Information:

Phone: (765) 494 8798
Email: sbasu [at] math.purdue.edu
Mailing Address:
Department of Mathematics
Purdue University
Rm. 742
150 N. University St., West Lafayette, IN 47907.

Book

Errata

New: The Second Edition of the book is now available online.

Download "Algorithms in Real Algebraic Geometry", Second Edition, by Saugata Basu, Richard Pollack, Marie-Françoise Roy. (Includes the interactive version.)

Research Interests

Real Algebraic and o-minimal Geometry, Computational Algebra and Geometry, Computational Complexity Theory.

New! I am co-organizing (with J.M. Landsberg and M. Rojas) a workshop on Mathematical aspects of the P vs NP problem and its variants at the new NSF math institute, ICERM, Providence, RI (Aug 1-5, 2011). Apply directly to ICERM via this link if interested in participating.

I also co-organize (with U. Walther, H. Schenk and A. Yong) the Illinois-Purdue Algebra, Geometry and Combinatorics Day held once every semester. Click here for more information.

Upcoming/Recent Talks and Events

Colloquium, McMaster University, Jan 18, 2013.
Model Theory Seminar, McMaster University, Jan 18, 2013.
Logic Seminar, Ohio State University, Oct 19, 2012.
Real Algebraic Geometry Seminar, Universite de Rennes 1 , May 24, 2012.
From Dynamics to Complexity A conference celebrating the work of Mike Shub May 07-11, 2012 hosted by the Fields Institute.
Geometry Seminar , Courant Institute of Mathematical Sciences, Feb 28, 2012. (Slides)
Computational Algebraic Geometry @ FoCM'11 July 8-10, 2011 Budapest, Hungary.
Real-number complexity@ FoCM'11 July 4-6, 2011 Budapest, Hungary.
Real Algebraic Geometry , Universite de Rennes 1, 20 - 24 June 2011. Conference Proceedings , Group photo .
International Conference on Algebra and Algebraic Geometry in honour of Prof. Shreeram S. Abhyankar on his 80th Birthday , (17th-22nd December 2010), Pune, India.
Mathematics Algorithms and Proofs 2010 , Logrono (Spain) 8-12th November 2010.
Convex Algebraic Geometry , Banff International Research Station, Canada, Feb 14 - 19, 2010. (Slides) (Group photo)
Oberwolfach Seminar on "New Trends in Algorithms for Real Algebraic Geometry" , Oberwolfach , Germany, Nov 22 - 28, 2009. Photos.
FOCS, Atlanta, Oct 25-27, 2009. Click here for link to video and slides from the talk.
Workshop on Complexity of Numerical Computation , Thematic Program on the Foundations of Computational Mathematics, Fields Institute, Toronto, Oct 20 - 24, 2009. Click here for link to audio presentation and slides from the talk.
Effective Methods in Algebraic Geometry (MEGA) , Barcelona, June 15-19, 2009. (Slides)
ACO Seminar , Georgia Tech, April 10, 2009. (Slides)
Geometry Seminar , Courant Institute of Mathematical Sciences, Feb 24, 2009. (Slides)
Seminar talk at IIT Kharagpur, CSE Department , Jan 13, 2009. (Slides)
Effective Real Analytic Geometry, ICMS, Edinburgh , May 5-9, 2008. (Slides)
Workshop on Enumeration and Bounds in Real Algebraic Geometry , Bernoulli Center, Lausanne, April 21-25, 2008. (Slides)
Geometry Seminar , Courant Institute of Mathematical Sciences, Mar 18, 2008. (Slides)
IMA Year on Applications of Algebraic Geometry Workshop on Complexity, Coding, and Communications, Minneapolis, April 16-20, 2007.
IMA, Algebraic Geometry and Applications Seminar, Minneapolis, April 11, 2007.
Seminaire de Geometrie Algebrique Reelle, IRMAR, Rennes , Feb 16, 2007. (Slides)
Oberwolfach Workshop on Geometric and Topological Combinatorics , Oberwolfach , Germany, Jan 28 - Feb 3, 2007. (Slides) (Report)
AMS-IMS-SIAM Joint Summer Research Conference, Discrete and Computational Geometry - Twenty Years Later, June 18 - 23, 2006, Snowbird, Utah. (Slides)
Special Trimester on Real Geometry, Fall 2005 Centre Emile Borel, Institut Henri Poincare, Paris, France Nov 1 - 30, 2005. Slides from advanced mini-course given at IHP. Lecture 1 , Lecture 2 , Lecture 3 , Lecture 4 .
Fourth Annual Network Meeting - RAAG 2005 September 5 - 9, 2005, Universitat Passau, Germany. (Slides) (Photo)
Foundations of Computational Mathematics (FOCM), 2005, Workshop on Real Number Complexity, Santander, Spain, July 7 - 9, 2005.
Workshop on Algorithms in Real Algebraic Geometry and Applications, (three one-hour lectures), Ouessant, France, June 24-28, 2005.
Computing the first few Betti numbers of semi-algebraic sets in singly exponential time, Effective Methods in Algebraic Geometry (MEGA) 2005, Porto Conte, Alghero, Sardinia, May 27-June1, 2005.
Efficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets, Colloquium, Department of Mathematics, University of Illinois, Urbana-Champaign, Sept 16, 2004.
Algorithmic Semi-algebraic Geometry: A Survey, Department of Computer Science, Indian Institute of Technology, Kharagpur, Aug 26, 2004.
Efficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets, Algebraic Topological Methods in Computer Science II, Department of Mathematics, University of Western Ontario, July 16-20, 2004.
Computing the Betti numbers of arrangements via spectral sequences, Session on Quantitative Results in Real Algebra and Geometry, First Joint Meeting between the RSME and the AMS, Seville, Spain, June 18-21, 2003.
Betti Numbers, Spectral Sequences and Algorithms, Workshop on Complexity, Foundations of Computational Mathematics, Minneapolis, August 5-14, 2002.
Computing the homology groups, Seminaire de Calcul formel et Complexite , Institut de Recherche Mathematique de Rennes, June 21, 2002.
Betti Numbers, Spectral Sequences and Algorithms for computing them, Workshop on Computations in Real Algebraic Geometry and Applications, Facultad de Ciencias, Universidad de Cantabria, Santander, Spain, June 13-15, 2002. (Slides)
New Bounds on the Betti Numbers of Semi-algebraic Sets and Algorithms for Computing them, Research Seminar at Research Institute for Symbolic Computation , Linz, Austria, June 4, 2002. (Slides)
New Bounds on the Betti Numbers of Semi-algebraic Sets and Algorithms for Computing them, CBMS Conference on Solving Polynomial Systems, College Station, Texas, May 21-24, 2002. (Slides)
Computing the Betti Numbers of Arrangements, 34th ACM Symposium on Theory of Computing Montreal, Quebec, Canada, May 19-21, 2002. (Slides)
New bounds for Betti numbers of semi-algebraic sets and algorithms for computing them, American Mathematical Society annual meeting in San Diego, Special Session on Computational Topology, Jan 8, 2002.
Algorithmic Semi-algebraic Geometry, Applied Mathematics Colloquium, University of Maryland, Baltimore County, Nov 16, 2001. (Slides)
On the topological complexity of semi-algebraic sets, Geometry and Topology Seminar, University of Georgia, Athens, Nov 12, 2001.
On the topological complexity of semi-algebraic sets, Conference on Real Algebraic Geometry, Rennes, France, June 11-15, 2001.
Different Bounds on the Different Betti Numbers of Semi-algebraic Sets, ACM Symposium on Computational Geometry, Medford, June 3-6, 2001. (Slides)
Topological and Combinatorial Complexity of Semi-algebraic Sets, DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry, Rutgers University, March 12-16, 2001. (Slides)

List of Publications

Refined bounds on the number of connected components of sign conditions on a variety II (with S. Barone).
Toric cubes are closed balls (with A. Gabrielov and N. Vorobjov), 2012.
A Helly-type theorem for semi-monotone sets and monotone maps (with A. Gabrielov and N. Vorobjov), 2012.
A baby step-giant step roadmap algorithm for general algebraic sets (with M.-F. Roy, M. Safey El Din, E. Schost), 2012.
Monotone functions and maps (with A. Gabrielov and N. Vorobjov) to appear in Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas , Special Issue: 80-th birthday of Heisuke Hironaka, 2012.
Algorithms in Real Algebraic Geometry: A Survey (paper version of the survey talk given at Real Algebraic Geometry Conference , Rennes, June 20-24, 2011).
Refined bounds on the number of connected components of sign conditions on a variety (with S. Barone), Discrete and Computational Geometry , 47:577-597 (2012).
On the homotopy types of limits of semi-algebraic sets and additive complexity of polynomials (with S. Barone), to appear in J. Eur. Math. Soc.
Semi-monotone sets (with A. Gabrielov and N. Vorobjov), to appear in J. Eur. Math. Soc.
A complex analogue of Toda's theorem , Foundations of Computational Mathematics , 2011.
Bounding the radii of balls meeting every connected component of semi-algebraic sets (with M.-F. Roy), Journal of Symbolic Computation , 45 (12):1270-1279, 2010 (special issue MEGA, 2009 ).
Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem (with T. Zell), Foundations of Computational Mathematics (2010) 10:429-454. An extended abstract appears in the Proceedings of FOCS (2009). A brief "two-page description" appears here .
Bounding the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials (with D. Pasechnik, M-F. Roy), J. Eur. Math. Soc. 12:529-553, 2010.
Combinatorial complexity in o-minimal geometry , Proc. London Math. Soc. , (3) 100 (2010) 405-428. (An extended abstract appeared in the Proceedings of ACM Symposium on Theory of Computing (STOC), 2007.)
Computing the Betti numbers and the Euler-Poincare characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials (with D. Pasechnik, M-F. Roy), Journal of Algebra, 321 (2009) 2206-2209.
An asymptotically tight bound on the number of connected components of realizable sign conditions , (with R. Pollack and M.-F. Roy) Combinatorica, 29 (5) (2009) 523-546.
Bounding the number of stable homotopy types of a parametrized family of semi-algebraic sets defined by quadratic inequalities (with M. Kettner), Proc. London Math. Soc. 39:4 (2008) 734-746.
On the number of topological types occurring in a parametrized family of arrangements , Discrete and Computational Geometry 40:481-503 (2008).
Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems , Surveys on Discrete and Computational Geometry: Twenty Years Later, Eds. J.E. Goodman, J. Pach, R. Pollack. Contemporary Mathematics, Volume: 453. American Mathematical Society 2008 .
A sharper estimate on the Betti numbers of sets defined by quadratic inequalities (with M. Kettner), Discrete and Computational Geometry 39:734-746, 2008.
Computing the first Betti number and the connected components of semi-algebraic sets (with R. Pollack and M-F. Roy), Foundations of Computational Mathematics , 8:97-136, 2008. (preliminary version appeared in Proceedings of STOC, 2005).
Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time, Foundations of Computational Mathematics 8:45-80, 2008. (preliminary version appeared in Proceedings of STOC, 2005).
Polynomial time algorithm for computing certain Betti numbers of the projections of semi-algebraic sets defined by few quadratic inequalities , (with T. Zell), Discrete and Computational Geometry , 39:100-122, 2008.
On the number of homotopy types of fibres of a definable map (with N. Vorobjov), J. London Math. Soc. , 76:757-776, 2007.
Efficient algorithm for computing the Euler-Poincare characteristic of semi-algebraic sets defined by few quadratic inequalities, Computational Complexity , 15 (2006), 236-251.
Computing the first few Betti numbers of semi-algebraic sets in single exponential time, Journal of Symbolic Computation , 41 (10):1125-1154, 2006.
On the Betti Numbers of Sign Conditions (with R. Pollack and M.-F. Roy), Proc. Amer. Math. Soc. 133 (2005), 965-974.
Computing the Euler-Poincare Characteristic of Sign Conditions (with R. Pollack and M.-F. Roy), Computational Complexity, 14 (2005) 53-71.
The Hadwiger transversal theorem for pseudolines (with A. Holmsen, J.E. Goodman, and R. Pollack), Current Trends in Combinatorial and Computational Geometry: Papers from the Special Program at MSRI, MSRI Publications Volume 52, Cambridge University Press 2005, 87-97.
Computing the Dimension of a Semi-Algebraic Set, (with R. Pollack and M.-F. Roy), Zap. Nauchn. Semin. POMI 316, 42-54 (2004).
On the combinatorial and topological complexity of a single cell , Discrete and Computational Geometry , 29:41-59, 2003.
Different Bounds on the Different Betti Numbers of Semi-algebraic Sets , Discrete and Computational Geometry , 30:65-85, 2003.
Computing Betti Numbers of Arrangements via Spectral Sequences, (for a better version click here: Postscript or PDF). Journal of Computer and System Sciences (special issue devoted to STOC 2002), 67 (2003) 244-262.
Computing Roadmaps of Semi-algebraic Sets on a Variety, (with R. Pollack and M.-F. Roy) Journal of the American Mathematical Society 13 (2000), 55-82.
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets , Discrete and Computational Geometry , 22:1-18 (1999).
New Results on Quantifier Elimination Over Real Closed Fields and Applications to Constraint Databases , Journal of the ACM, 46 (4), 1999.
On Computing a Set of Points meeting every Semi-algebraically Connected Component of a Family of Polynomials on a Variety (with R. Pollack and M.-F. Roy), Journal of Complexity, 13(1):28-37 (1997).
On the Combinatorial and Algebraic Complexity of Quantifier Elimination (journal version) (with R. Pollack and M.-F. Roy), Journal of the ACM , 4(6): 1002 - 1046 (1996).
On the number of cells defined by a family of polynomials on a variety (with R. Pollack and M.-F. Roy), Mathematika, 43 (1996) 120-126.
Design of CAECC --Cellular Automata Based Error Correcting Code, IEEE Transactions on Computers (with D. Roy Chowdhury, I. Sengupta, P. Pal Chaudhuri), 43 (6) 1994.

Conference Publications

A New Algorithm to find a point in every cell defined by a family of polynomials (with R. Pollack and M.-F. Roy), in Quantifier Elimination and Cylindrical Algebraic Decomposition, B. Caviness and J. Johnson Eds., Springer-Verlag.
Computing a set of points meeting every cell defined by a family of polynomials on a variety (with R. Pollack and M.-F. Roy), in Algorithmic Foundations of Robotics, (WAFR) K.Y. Goldberg, D. Halperin, J.-C. Latombe, R.H. Wilson, Eds., A.K. Peters, Boston, 1994.
On the Combinatorial and Algebraic Complexity of Quantifier Elimination (extended abstract) (with R. Pollack and M.-F. Roy), FOCS 1994.
Constructing Roadmaps of Semi-algebraic Sets (with R. Pollack and M.-F. Roy), STOC 1996.
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets , STOC 1996.
Computing Roadmaps of Semi-algebraic Sets on a Variety (extended abstract) (with R. Pollack and M.-F. Roy), FOCM 1997.
Uniform Quantifier Elimination and Constraint Query Processing , ISSAC 1997.
An Improved Algorithm for Quantifier Elimination Over Real Closed Fields , FOCS 1997.
Complexity of Computing Semi-algebraic Descriptions of the Connected Components of Semi-Algebraic Sets (with R. Pollack and M.-F. Roy), ISSAC 1998.
On the Combinatorial and Topological Complexity of a Single Cell , FOCS 1998.
Different Bounds on the Different Betti Numbers of Semi-algebraic Sets , SoCG 2001.
Computing the Betti Numbers of Arrangements STOC 2002.
Polynomials that sign represent parity and Descartes' rule of signs (with N. Bhatnagar, P. Gopalan, R. Lipton), IEEE Conference on Computational Complexity, 2004.

Saugata Basu

Professor

Department of Mathematics

Purdue University

Contact Information:

Table of Contents

Book

Volumes Edited

Teaching Spring 2013

Research Interests

Vitae

Upcoming/Recent Talks and Events

List of Publications