Saugata Basu

Publication Activity (10 Years)

Years Active: 1992-2024
Publications (10 Years): 25

Top Topics

Delaunay Triangulations

Algebraic Geometry

Gene Expression

Persistent Homology

Top Venues

Discret. Comput. Geom.

SIAM J. Appl. Algebra Geom.

Found. Comput. Math.

Publications

Saugata Basu, Nathanael Cox
Harmonic Persistent Homology. SIAM J. Appl. Algebra Geom. 8 (1) (2024)
Saugata Basu, Ali Mohammad Nezhad
On the complexity of analyticity in semi-definite optimization. Adv. Appl. Math. 156 (2024)
Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen
Randomized Functions with High Round Complexity. TCC (1) (2023)
Saugata Basu, Negin Karisani
Persistent Homology of Semialgebraic Sets. SIAM J. Appl. Algebra Geom. 7 (3) (2023)
Saugata Basu, Laxmi Parida
Quantum Analog of Shannon's Lower Bound Theorem. CoRR (2023)
Saugata Basu, Ali Mohammad Nezhad
On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate. SIAM J. Appl. Algebra Geom. 6 (2) (2022)
Saugata Basu, Cordian Riener
Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets. Found. Comput. Math. 22 (5) (2022)
Saugata Basu, Nathanael Cox
Harmonic Persistent Homology (extended abstract). FOCS (2022)
Saugata Basu, Negin Karisani, Laxmi Parida
Sequents, barcodes, and homology. CoRR (2022)
Saugata Basu, Nathanael Cox, Sarah Percival
On the Reeb Spaces of Definable Maps. Discret. Comput. Geom. 68 (2) (2022)
Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen
Geometry of Secure Two-party Computation. FOCS (2022)
Saugata Basu, Nathanael Cox
Harmonic Persistent Homology (extended abstract). FOCS (2021)
Saugata Basu, Antonio Lerario
Hausdorff approximations and volume of tubes of singular algebraic sets. CoRR (2021)
Negin Karisani, Daniel E. Platt, Saugata Basu, Laxmi Parida
Inferring COVID-19 Biological Pathways from Clinical Phenotypes via Topological Analysis. CoRR (2021)
Sayan Mandal, Aldo Guzmán-Sáenz, Niina Haiminen, Saugata Basu, Laxmi Parida
A Topological Data Analysis Approach on Predicting Phenotypes from Gene Expression Data. AlCoB (2020)
Aldo Guzmán-Sáenz, Niina Haiminen, Saugata Basu, Laxmi Parida
Signal enrichment with strain-level resolution in metagenomes using topological data analysis. BMC Genom. 20 (S2) (2019)
Saugata Basu, Anthony Rizzie
Multi-degree Bounds on the Betti Numbers of Real Varieties and Semi-algebraic Sets and Applications. Discret. Comput. Geom. 59 (3) (2018)
Saugata Basu, Nathanael Cox, Sarah Percival
On the Reeb spaces of definable maps. CoRR (2018)
Saugata Basu, Filippo Utro, Laxmi Parida
Essential Simplices in Persistent Homology and Subtle Admixture Detection. WABI (2018)
Saugata Basu, Orit E. Raz
An o-minimal Szemerédi-Trotter theorem. CoRR (2016)
Saugata Basu, Martín Sombra
Polynomial Partitioning on Varieties of Codimension Two and Point-Hypersurface Incidences in Four Dimensions. Discret. Comput. Geom. 55 (1) (2016)
Saugata Basu, Cordian Riener
Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets. CoRR (2016)
Daniel E. Platt, Saugata Basu, Pierre A. Zalloua, Laxmi Parida
Characterizing redescriptions using persistent homology to isolate genetic pathways contributing to pathogenesis. BMC Syst. Biol. 10 (S-1) (2016)
Saugata Basu, Cordian Riener
On the equivariant Betti numbers of symmetric semi-algebraic sets: vanishing, bounds and algorithms. CoRR (2016)
Saugata Basu, M. Umut Isik
Categorical Complexity. CoRR (2016)
Saugata Basu, Anthony Rizzie
Multi-degree bounds on the Betti numbers of real varieties and semi-algebraic sets and applications. CoRR (2015)
Laxmi Parida, Filippo Utro, Deniz Yörükoglu, Anna Paola Carrieri, David Kuhn, Saugata Basu
Topological Signatures for Population Admixture. RECOMB (2015)
Saugata Basu, Cordian Riener
On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities. CoRR (2015)
Saugata Basu
A Complexity Theory of Constructible Functions and Sheaves. Found. Comput. Math. 15 (1) (2015)
Saugata Basu
Algorithms in Real Algebraic Geometry: A Survey. CoRR (2014)
Saugata Basu, Marie-Françoise Roy
Divide and Conquer Roadmap for Algebraic Sets. Discret. Comput. Geom. 52 (2) (2014)
Saugata Basu, Martín Sombra
Polynomial partitioning on varieties and point-hypersurface incidences in four dimensions. CoRR (2014)
Saugata Basu, Marie-Françoise Roy, Mohab Safey El Din, Éric Schost
A Baby Step-Giant Step Roadmap Algorithm for General Algebraic Sets. Found. Comput. Math. 14 (6) (2014)
Saugata Basu, Cordian Riener
Bounding the equivariant Betti numbers and computing the generalized Euler-Poincaré characteristic of symmetric semi-algebraic sets. CoRR (2013)
Saugata Basu, Laxmi Parida
Spectral Sequences, Exact Couples and Persistent Homology of filtrations. CoRR (2013)
Saugata Basu
A complexity theory of constructible functions and sheaves. CoRR (2013)
Saugata Basu, Andrei Gabrielov, Nicolai N. Vorobjov Jr.
A Helly-Type Theorem for Semi-monotone Sets and Monotone Maps. Discret. Comput. Geom. 50 (4) (2013)
Saugata Basu, Marie-Françoise Roy, Mohab Safey El Din, Éric Schost
A baby step-giant step roadmap algorithm for general algebraic sets CoRR (2012)
Saugata Basu
A Complex Analogue of Toda's Theorem. Found. Comput. Math. 12 (3) (2012)
Sal Barone, Saugata Basu
Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety. Discret. Comput. Geom. 47 (3) (2012)
Sal Barone, Saugata Basu
Refined bounds on the number of connected components of sign conditions on a variety CoRR (2011)
Saugata Basu, Thierry Zell
Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda's Theorem. Found. Comput. Math. 10 (4) (2010)
Saugata Basu, Marie-Françoise Roy
Bounding the radii of balls meeting every connected component of semi-algebraic sets. J. Symb. Comput. 45 (12) (2010)
Saugata Basu
A complex analogue of Toda's Theorem. Electron. Colloquium Comput. Complex. 16 (2009)
Saugata Basu, Thierry Zell
Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem. FOCS (2009)
Saugata Basu, Richard Leroy, Marie-Françoise Roy
A bound on the minimum of a real positive polynomial over the standard simplex CoRR (2009)
Saugata Basu, Marie-Françoise Roy
Bounding the radii of balls meeting every connected component of semi-algebraic sets CoRR (2009)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions. Comb. 29 (5) (2009)
Saugata Basu
A complex analogue of Toda's Theorem CoRR (2009)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Computing the First Betti Number of a Semi-Algebraic Set. Found. Comput. Math. 8 (1) (2008)
Saugata Basu, Thierry Zell
Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem CoRR (2008)
Saugata Basu
On the Number of Topological Types Occurring in a Parameterized Family of Arrangements. Discret. Comput. Geom. 40 (4) (2008)
Saugata Basu
Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time. Found. Comput. Math. 8 (1) (2008)
Saugata Basu, Thierry Zell
On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities. Discret. Comput. Geom. 39 (1-3) (2008)
Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Polynomials that Sign Represent Parity and Descartes' Rule of Signs. Comput. Complex. 17 (3) (2008)
Saugata Basu
Errata for Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time. Found. Comput. Math. 8 (1) (2008)
Saugata Basu, Michael Kettner
A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities. Discret. Comput. Geom. 39 (4) (2008)
Saugata Basu
Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems CoRR (2007)
Saugata Basu, Dmitrii V. Pasechnik, Marie-Françoise Roy
Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials CoRR (2007)
Saugata Basu
Combinatorial complexity in O-minimal geometry. STOC (2007)
Saugata Basu
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities. Comput. Complex. 15 (3) (2006)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Computing the First Betti Numberand Describing the Connected Components of Semi-algebraic Sets CoRR (2006)
Saugata Basu
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities CoRR (2006)
Saugata Basu
Computing the first few Betti numbers of semi-algebraic sets in single exponential time. J. Symb. Comput. 41 (10) (2006)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
An asymptotically tight bound on the number of connected components of realizable sign conditions CoRR (2006)
Saugata Basu
Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time CoRR (2006)
Saugata Basu
Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time CoRR (2006)
Saugata Basu, Michael Kettner
Computing the Betti Numbers of Arrangements in Practice. CASC (2005)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Computing the euler-poincaré characteristics of sign conditions. Comput. Complex. 14 (1) (2005)
Saugata Basu
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. STOC (2005)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Computing the first Betti number and the connected components of semi-algebraic sets. STOC (2005)
Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Polynomials That Sign Represent Parity and Descartes Rule of Signs. Computational Complexity Conference (2004)
Saugata Basu, Raghavan Dhandapani, Richard Pollack
. Graph Drawing (2004)
Saugata Basu
Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets. Discret. Comput. Geom. 30 (1) (2003)
Saugata Basu
Computing the Betti numbers of arrangements via spectral sequences. J. Comput. Syst. Sci. 67 (2) (2003)
Saugata Basu
The Combinatorial and Topological Complexity of a Single Cell. Discret. Comput. Geom. 29 (1) (2003)
Saugata Basu
Computing the betti numbers of arrangements. STOC (2002)
Saugata Basu
Different bounds on the different Betti numbers of semi-algebraic sets. SCG (2001)
Saugata Basu
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets. Discret. Comput. Geom. 22 (1) (1999)
Saugata Basu
New Results on Quantifier Elimination over Real Closed Fields and Applications to Constraint Databases. J. ACM 46 (4) (1999)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Complexity of Computing Semi-Algebraic Descriptions of the Connected Components of a Semi-Algebraic Set. ISSAC (1998)
Saugata Basu
On the Combinatorial and Topological Complexity of a Single Cell. FOCS (1998)
Saugata Basu
An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. FOCS (1997)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
On Computing a Set of Points Meeting Every Cell Defined by a Family of Polynomials on a Variety. J. Complex. 13 (1) (1997)
Saugata Basu
Uniform Quantifier Elimination and Constraint Query Processing. ISSAC (1997)
Saugata Basu
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets. STOC (1996)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract). STOC (1996)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
On the Combinatorial and Algebraic Complexity of Quantifier Elimination. J. ACM 43 (6) (1996)
Dipanwita Roy Chowdhury, Saugata Basu, Idranil Sen Gupta, Parimal Pal Chaudhuri
Design of CAECC-Cellular Automata Based Error Correcting Code. IEEE Trans. Computers 43 (6) (1994)
Saugata Basu, Richard Pollack, Marie-Françoise Roy
On the Combinatorial and Algebraic Complexity of Quantifier Elimination FOCS (1994)
Dipanwita Roy Chowdhury, Saugata Basu, Idranil Sen Gupta, Parimal Pal Chaudhuri
A Novel Scheme for Designing Error Correcting Codes Using Cellular Automata. VLSI Design (1992)