Saugata Basu

Table of Contents

• Book
• Volumes Edited
• Teaching
• Research Interests
• Vitae
• Research Summary
• Upcoming and Recent Trips
• List of Publications

Book

Errata

New: Downloading Algorithms in Real Algebraic Geometry, Saugata Basu, Richard Pollack, Marie-Françoise Roy. (Includes the interactive version)

Volumes Edited

Teaching Fall 2007

• Graduate Algebra I, Math 6121.

• (Undergraduate) Abstract Algebra I, Math 4107.

Research Interests

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

Vitae

CV (.PDF), (.PS).

Research Summary

Research Statement (.PDF), (.PS).

Upcoming and Recent Talks

• 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 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 (in press).

    ---

  • 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 (in press).

    ---

  • Combinatorial Complexity in O-minimal Geometry , submitted. (An extended abstract appeared in the Proceedings of ACM Symposium on Theory of Computing (STOC), 2007.)

    ---

  • 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 (in press).

    ---

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

    ---

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

    ---

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

    ---

  • 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 Betti number and the connected components of semi-algebraic sets (with R. Pollack and M-F. Roy), to appear in Foundations of Computational Mathematics , (preliminary version appeared in Proceedings of STOC, 2005).

    ---

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

    ---

  • Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time, to appear in Foundations of Computational Mathematics (preliminary version appeared in Proceedings of STOC, 2005).

    ---

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

    ---

  • 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 the Dimension of a Semi-Algebraic Set, (with R. Pollack and M.-F. Roy), Zap. Nauchn. Semin. POMI 316, 42-54 (2004).

    ---

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

    ---

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

    ---

  • 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 Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets , Discrete and Computational Geometry , 22:1-18, (1999).

    ---

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