Saugata Basu

Professor

Contact Information:

Table of Contents

• Book
• Volumes Edited
• Teaching
• Research Interests
• Vitae
• Activities
• Upcoming and Recent Talks
• List of Publications

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.)

Volumes Edited

Teaching Fall 2008

• Abstract Algebra I, Math 557.

• (Undergraduate) Linear Algebra, Math 265.

Teaching Fall 2009

• (Undergraduate) Linear Algebra, Math 265.

Research Interests

Real Algebraic Geometry, Computational Algebra and Geometry, Theoretical Computer Science.

Vitae

CV (.PDF), (.PS).

Fall 2009 Activities

• Oberwolfach Seminar on "New Trends in Algorithms for Real Algebraic Geometry" , Nov 24 - 28, 2009. This seminar is directed towards graduate students and young researchers. If you are interested in attending, please apply directly to Oberwolfach by October 15.
• Illinois-Purdue Algebra, Geometry and Combinatorics Day , Sep 26, 2009.
• Real Algebraic and Analytic Geometry at Purdue.

Upcoming and Recent Talks and Events

• Convex Algebraic Geometry , Banff International Research Station, Canada, Feb 14 - 19, 2010.
• Oberwolfach Seminar on "New Trends in Algorithms for Real Algebraic Geometry" , Oberwolfach , Germany, Nov 24 - 28, 2009.
• 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 Montréal, Québec, 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 and Analytic 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

• Journal Publications
  • Bounding the radii of balls meeting every connected component of semi-algebraic sets (with M.-F. Roy), submitted.

    ---

  • Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem (with T. Zell), to appear in Foundations of Computational Mathematics . An extended abstract to appear in the Proceedings of FOCS (2009). A brief "two-page description" appears here .

    ---

  • 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.

    ---

  • Bounding the number of stable homotopy types of a parametrized family of semi-algebraic sets defined by quadratic inequalities (with M. Kettner), Proceedings of the London Mathematical Society 39:4 (2008) 734-746.

    ---

  • Bounding the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials (with D. Pasechnik, M-F. Roy), Journal of the European Mathematical Society (in press).

    ---

  • On the number of topological types occurring in a parametrized family of arrangements , Discrete and Computational Geometry 40:481-503 (2008).

    ---

  • Combinatorial Complexity in O-minimal Geometry , to appear in the Proceedings of the London Mathematical Society , 2009. (An extended abstract appeared in the Proceedings of ACM Symposium on Theory of Computing (STOC), 2007.)

    ---

  • An asymptotically tight bound on the number of connected components of realizable sign conditions , (with R. Pollack and M.-F. Roy) to appear in Combinatorica .

    ---

  • 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 Vol 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 , Vol 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 Vol 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 , Vol 39, 100-122, 2008.

    ---

  • On the number of homotopy types of fibres of a definable map (with N. Vorobjov), Journal of the London Mathematical Society , Vol 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 , Volume 41, Issue 10, October 2006, 1125-1154.

    ---

  • 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, Vol 46, No. 4, July, 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, March 1997, Vol 13, Number 1, 28-37.

    ---

  • On the Combinatorial and Algebraic Complexity of Quantifier Elimination (journal version) (with R. Pollack and M.-F. Roy), Journal of the ACM , Nov 1996, Vol 43, Number 6, 1002 - 1046.

    ---

  • 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), Vol. 43, Number 6, June,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.