Saugata Basu

Professor

Department of Mathematics

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

Volumes Edited

Teaching: Fall, 2024

Linear Algebra (Math 554).

Current Research Interests

Real algebraic and o-minimal geometry, model theory and combinatorics, computational complexity theory, applied topology.

Upcoming/Recent Talks and Events

SIAM Conference on Applied Algebraic Geometry 2025, University of Wisconsin-Madison, Madison, Wisconsin, July 7-11, 2025.
MFO-RIMS Tandem Workshop: Optimization, Theoretical Computer Science and Algebraic Geometry: Convexity and Beyond , Oberwolfach, 16 Feb - 21 Feb 2025.
2024 Lie-Stormer Colloquium Foundational and computational aspects of symmetry , Tromso, Norway, Dec 2-4, 2024.
CAM Colloquium, University of Chicago , Nov 21, 2024.
Math/CS Colloquium, Wabash College , Nov 19, 2024.
Positive Solutions of Polynomial Systems Arising from Real-life Applications (24w5197) , BIRS, Granada, May 19-24, 2024.
OAL-RAG 2024, A conference on Order, Algebra, Logic, and Real Algebraic Geometry , Baton Rouge, May 9 - May 11, 2024.
Symmetry, Stability, and interactions with Computation , CIRM, Luminy, 13-17, Nov, 2023.
Workshop on Real Number Complexity , FoCM, Paris, Jun 15-17, 2023.
BIRS workshop on Random Algebraic Geometry , Banff, April 16-21, 2023.
Applied Topology Seminar (virtual), April 12, 2023.
Oberwolfach Workshop on New Directions in Real Algebraic Geometry , Oberwolfach, Mar 19-25, 2023.
Virtual Commutative Algebra Seminars, Feb 10, 2023.
Seminar talk at Stat-Math, Indian Statistical Institute , Kolkata, Dec 13, 2022.
Real Algebraic Geometry (4 lectures), CIRM, Luminy, 24 - 28 October 2022.
Real algebraic geometry and singularities, Conference in honor of Wojciech Kucharz's 70th birthday , Krakow, 12-17 Sep, 2022.
Latin American Geometria Algebraica Real y TrOpical Seminar (LAGARTOS), Aug 26, 2022.
ATMCS 10 (Algebraic Topology: Methods, Computation, & Science) , Oxford University, June 20-24, 2022.
Conference "On the Crossroad of Topology and Enumerative Geometry" , Leonhard Euler International Mathematical Institute in Saint Petersburg, 13-17 June, 2022 (cancelled).
Mathematics Colloquium , Department of Mathematics, University at Albany, Dec 3, 2021.
Workshop on Model Theory and Combinatorics, November 29 - December 3, 2021, The Fields Institute.
MFO-RIMS Tandem Workshop: Symmetries on Polynomial Ideals and Varieties (hybrid meeting), Sep 5-11, 2021.
Symmetry, Randomness, and Computations in Real Algebraic Geometry , Aug 24 - 28, 2020, ICERM, Providence, RI.
Workshop on Real Number Complexity, FoCM, 2020 , Simon Fraser University, Vancouver BC, Jun 18-20, 2020.
Real Geometry Seminar (online) SISSA, Trieste, May 12, 2020.
Geometrie Algebrique Reele , CIRM, Luminy, 20 - 24 April, 2020.
Special Session on Model Theory and its Applications , Spring Central Sectional Meeting Purdue University, West Lafayette, IN April 4-5, 2020.
MPS Conference on Discrete & Computational Geometry: Quo Vadis (Dedicated to the memory of Ricky Pollack) , Flatiron Institute New York, March 30 - April 3, 2020.
Algebraic Methods in Discrete and Computational Geometry , Portland, Oregon, June 18-21, 2019. Slides.
Geometry of Real Polynomials, Convexity and Optimization , Banff International Research Station, May 26-31, 2019. Video .
A^3 -- Arctic Applied Algebra Conference, UiT, Tromso, Norway, April 1 - 5, 2019.
TGDA Seminar, Ohio State, May 1, 2018.
Algebraic Geometry Seminar, Purdue University, April 18, 2018.
Geometry Seminar, Courant Institute, April 3, 2018.
Two seminar talks at the Stat-Math Unit, Indian Statistical Institute, Kolkata, Mar 19 and 21, 2018.
Workshop on Numerical Methods for Algebraic Curves, Rennes, Feb 18 -Feb 23, 2018.
Workshop on Model theory and Combinatorics, IHP, Paris , Jan 29 -Feb 02, 2018. Video.
Computability in Europe, Special Session on Computability in analysis, algebra, and geometry, organized by Julia Knight (Notre Dame, USA) and Andrey Morozov (Novosibirsk, Russia) , Jun 12-16, 2017.
Oberwolfach Workshop on O-Minimality and its Applications to Number Theory and Analysis , April 30- May 6, 2017.
Workshop on Topology: Identifying Order in Complex Systems, Rutgers University , April 1, 2017.
Conference on Real Algebraic Geometry, Nagoya University, Mar 13-19, 2017.
Shanks Workshop on Real Algebraic Geometry, Vanderbilt University , Mar 10-11, 2017.
Logic Seminar, Department of Mathematics, University of Notre Dame , Feb 14, 2017.
Combinatorial and Computational Geometry Reunion Conference II , December 11 - 16, 2016.
Mathematics Colloquium , School of Mathematics, Georgia Tech , Sept 15, 2016.
Conference on Statistical Topology of Random Manifolds: Theory and Applications, The Abdus Salam International Centre for Theoretical Physics (ICTP), Trieste, July 18-23, 2016.
Workshop on Algebra, Geometry and Proofs in Symbolic Computation Dec 7-16, 2015, Fields Institute.
Symbolic-Numeric Computing Seminar Nov 20, 2015, CUNY, Graduate Center. Slides.
Structures algébriques ordonnées et leurs interactions 12 au 16 Octobre 2015 CIRM, Luminy. Slides . Group Photo .
Complexity of Symbolic and Numerical Problems, June 7- 12, 2015, Dagstuhl Seminar 15242. Slides .
Computability, Analysis, and Geometry, BIRS, Mar 8-13, 2015. Video .
Real singularities and applications, February 16-20 2015 CIRM, Luminy.
Solving Polynomial Equations, Simon's Institute for the Theory of Computing, Berkeley, Oct 13-16, 2014. Video and slides .
Algebraic Techniques for Combinatorial and Computational Geometry: Culminating Workshop Lake Arrowhead, UCLA, Jun 8 - 13, 2014.
University of Chicago Algebraic Geometry Seminar , April 23, 2014.
Algebraic Techniques for Combinatorial and Computational Geometry Workshop II: Tools from Algebraic Geometry IPAM, UCLA, April 7 - 11, 2014. Video .
Algebraic Techniques for Combinatorial and Computational Geometry Workshop I: Combinatorial Geometry Problems at the Algebraic Interface IPAM, UCLA, March 24 - 28, 2014. Video .
Algebraic Techniques for Combinatorial and Computational Geometry Combinatorial and Computational Geometry: Tutorials , IPAM, UCLA, March 11 - 14, 2014. Videos Lecture 1 , Lecture 2 .
Applications of Real Algebraic Geometry , Helsinki, Finland, Feb 27-Mar 2, 2014.
Geometry Seminar , Courant Institute, Feb 18, 2014.
Talk at the math department, RKMV University, Kolkata, Feb 5, 2014.
Polyhedra, Lattices, Algebra, and Moments , Inverse Moment Problems: the Crossroads of Analysis, Algebra, Discrete Geometry and Combinatorics, IMS, Singapore Jan 6-17, 2014.
Geometry Seminar, Courant Institute, April 16, 2013.
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

Cohomological VC-density: Bounds and Applications (with Deepam Patel).
Bounds on the realizations of zero-nonzero patterns and sign conditions of polynomials restricted to varieties and applications (with Laxmi Parida).
Complexity and speed of semi-algebraic multi-persistence (with Arindam Banerjee).
Improved effective Lojasiewicz inequality and applications (with Ali Mohammad-Nezhad). To appear in Forum of Mathematics, Sigma.
A stationary set method for estimating oscillatory integrals (with Shaoming Guo, Ruixiang Zhang, Pavel Zorin-Kranich). To appear in J. Eur. Math. Soc.
Harmonic Persistent Homology (with Nathanael Cox). SIAM Journal on Applied Algebra and Geometry, Vol 8, Issue 1 (2024) doi.org/10.1137/22M15187.
Marie-Francoise Roy . Notices of the American Mathematical Society, March, 2024.
Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set (with Sarah Percival). Discrete Comput Geom (2024). https://doi.org/10.1007/s00454-024-00626-0
Computing the homology functor on semi-algebraic maps and diagrams (with Negin Karisani). Discrete Comput Geom, (2024). https://doi.org/10.1007/s00454-024-00627-z
On the complexity of analyticity in semi-definite optimization (with Ali Mohammad-Nezhad), Advances in Applied Mathematics, Volume 156, 2024.
Randomized Functions with High Round Complexity (with Hamidreza Amini Khorasgani, Hemanta Maji K. and Hai H. Nguyen). Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14369. Springer, Cham. https://doi.org/10.1007/978-3-031-48615-9_12.
Persistent homology of semi-algebraic sets (with Negin Karisani). SIAM Journal on Applied Algebra and Geometry, Vol. 7, Issue 3 (2023) doi 10.1137/22M1494415.
Efficient simplicial replacement of semi-algebraic sets (with Negin Karisani). Forum of Mathematics, Sigma, 11, E41. doi:10.1017/fms.2023.36.
Topology of real multi-affine hypersurfaces and a homological stability property (with Daniel Perrucci). Advances in Mathematics , Volume 420, 1 May 2023.
Geometry of Secure Two-party Computation (with Hamidreza Amini Khorasgani, Hemanta Maji K. and Hai H. Nguyen). Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2022 .
Hausdorff approximations and volume of tubes of singular algebraic sets (with Antonio Lerario), Mathematische Annalen (2022). doi:10.1007/s00208-022-02458-w.
Betti Numbers of Random Hypersurface Arrangements (with Antonio Lerario and Abhiram Natarajan), J. London Math. Soc. (2022). doi:10.1112/jlms.1265.
On the central path of semidefinite optimization: Degree and worst-case convergence rate (with Ali Mohammad-Nezhad), SIAM Journal on Applied Algebra and Geometry (2022), Vol 6, Issue 2, doi:10.1137/21M1419933.
On the Reeb spaces of definable maps (with N. Cox, S. Percival), Discrete Comput Geom (2022). doi:10.1007/s00454-022-00400-0.
Quantitative Curve Selection Lemma (with M.-F. Roy). Mathematische Zeitschrift (2021). doi:10.1007/s00209-021-02837-0.
Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets (with Cordian Riener). Found Comput Math . Electronically published on Aug 2, 2021. doi:10.1007/s10208-021-09519-7.
VC density of definable families over valued fields (with Deepam Patel), J. Eur. Math. Soc. Vol 23, Number 7, 2361-2403, 2021.
Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem (with Deepam Patel), Selecta Mathematica, New Series, (2020) pages 26-71, doi:10.1007/s00029-020-00596-0.
Categorical complexity (with U. Isik), Forum of Mathematics, Sigma, (2020), Vol. 8, e34, 63 pages, doi:10.1017/fms.2020.26.
On the isotypic decomposition of the cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities (with C. Riener), International Mathematics Research Notices, (7):2054-2113, 2020.
Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare (with A. Lerario, A. Natarajan), Quarterly Journal of Mathematics , Volume 70, Issue 4, Pages 1397-1409, December 2019.
Random fields and the enumerative geometry of lines on real and complex hypersurfaces (with A. Lerario, E. Lundberg, and C. Peterson), Mathematische Annalen , Volume 374, Issue 3-4, pp 1773-1810, August 2019.
On the equivariant Betti numbers of symmetric semi-algebraic sets: vanishing, bounds and algorithms (with C. Riener), Selecta Mathematica, New Series, 24(4), 3241-3281 (2018).
Multi-degree bounds on the Betti numbers of real varieties and semi-algebraic sets and applications (with A. Rizzie), Discrete and Computational Geometry, Volume 59, Issue 3, pp 553-620, April 2018.
An o-minimal Szemeredi-Trotter Theorem (with O. Raz), Quarterly Journal of Mathematics ,Volume 69, Issue 1, Pages 223-239, March 2018.
Efficient algorithms for computing the Euler-Poincare characteristics of symmetric semi-algebraic sets (with C. Riener), Ordered Algebraic Structures and Related Topics, Contemporary Mathematics, 697, 53-81, 2017.
Algorithms in Real Algebraic Geometry: A Survey , Panoramas et syntheses 51, 107-153, 2017.
Spectral sequences, exact couples and persistent homology of filtrations (with L. Parida), Expositiones Mathematicae , Volume 35, Issue 1, March 2017, Pages 119-132, 2017. (This is the corrected version. Errata for the published version ).
Bounding the equivariant Betti numbers of symmetric semi-algebraic sets (with C. Riener), Advances in Mathematics , 305:803-855, January 2017.
On a real analogue of Bezout inequality and bounds on the number of connected components of sign conditions (with S. Barone), Proc. London Math. Soc. , (3) 112 (2016), no. 1, 115-145.
Polynomial partitioning on varieties of codimension two and point-hyperface incidences in four dimensions (with M. Sombra), Discrete and Computational Geometry ), 55 (1), 158-184, 2016.
Triangulations of monotone families I: two-dimensional families (with A. Gabrielov and N. Vorobjov), Proceedings of the London Mathematical Society , 111(5):1013-1051, 2015.
A complexity theory of constructible functions and sheaves , Foundations of Computational Mathematics , February 2015, Volume 15, Issue 1, pp 199-279.
On the homotopy types of limits of semi-algebraic sets and additive complexity of polynomials (with S. Barone), J. Eur. Math. Soc. Vol 16, 1527-1554, 2014.
Divide and conquer roadmap for algebraic sets (with M.-F. Roy), Discrete and Computational Geometry , Volume 52, Issue 2, pp 278-343, 2014.
A baby step-giant step roadmap algorithm for general algebraic sets (with M.-F. Roy, M. Safey El Din, E. Schost), Foundations of Computational Mathematics , December 2014, Volume 14, Issue 6, pp 1117-1172.
A Helly-type theorem for semi-monotone sets and monotone maps (with A. Gabrielov and N. Vorobjov), Discrete and Computational Geometry , Volume 50, Issue 4, pp 857-864, 2013.
Monotone functions and maps (with A. Gabrielov and N. Vorobjov) Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas , Volume 107, Issue 1, March 2013, 5-33. (Special Issue: 80-th birthday of Heisuke Hironaka).
Semi-monotone sets (with A. Gabrielov and N. Vorobjov), J. Eur. Math. Soc. , Volume 15, Issue 2, 2013 (635-657).
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).
A complex analogue of Toda's theorem , Foundations of Computational Mathematics , June 2012, Volume 12, Issue 3, pp 327-362.
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.