% csauthors.net - beta - BibTeX bibliography of Saugata Basu
@inproceedings{conf/vlsid/ChowdhuryBGC92,
title = {A Novel Scheme for Designing Error Correcting Codes Using Cellular Automata.},
year = {1992},
booktitle = {VLSI Design},
author = {{Dipanwita Roy Chowdhury} and {Saugata Basu} and {Idranil Sen Gupta} and {Parimal Pal Chaudhuri}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the Fifth International Conference on VLSI Design, VLSI Design 1992, Bangalore, India, January 4-7, 1992}
}
@article{journals/tc/ChowdhuryBGC94,
title = {Design of CAECC-Cellular Automata Based Error Correcting Code.},
year = {1994},
journal = {IEEE Trans. Computers},
author = {{Dipanwita Roy Chowdhury} and {Saugata Basu} and {Idranil Sen Gupta} and {Parimal Pal Chaudhuri}}
}
@inproceedings{conf/stoc/BasuPR96,
title = {Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract).},
year = {1996},
booktitle = {STOC},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}},
publisher = {ACM},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996}
}
@article{journals/jacm/BasuPR96,
title = {On the Combinatorial and Algebraic Complexity of Quantifier Elimination.},
year = {1996},
journal = {J. ACM},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@phdthesis{phd/us/Basu96,
title = {Algorithms in Semi-Algabraic Geometry.},
year = {1996},
author = {{Saugata Basu}}
}
@inproceedings{conf/focs/Basu97,
title = {An Improved Algorithm for Quantifier Elimination Over Real Closed Fields.},
year = {1997},
booktitle = {FOCS},
author = {{Saugata Basu}},
publisher = {IEEE Computer Society},
booktitle = {38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997}
}
@inproceedings{conf/issac/Basu97,
title = {Uniform Quantifier Elimination and Constraint Query Processing.},
year = {1997},
booktitle = {ISSAC},
author = {{Saugata Basu}},
publisher = {ACM},
booktitle = {Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC 1997, Maui, Hawaii, USA, July 21-23, 1997}
}
@article{journals/jc/BasuPR97,
title = {On Computing a Set of Points Meeting Every Cell Defined by a Family of Polynomials on a Variety.},
year = {1997},
journal = {J. Complex.},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@inproceedings{conf/issac/BasuPR98,
title = {Complexity of Computing Semi-Algebraic Descriptions of the Connected Components of a Semi-Algebraic Set.},
year = {1998},
booktitle = {ISSAC},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}},
publisher = {ACM},
booktitle = {Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC '98, Rostock, Germany, August 13-15, 1998}
}
@article{journals/dcg/Basu99,
title = {On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets.},
year = {1999},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu}}
}
@article{journals/jacm/Basu99,
title = {New Results on Quantifier Elimination over Real Closed Fields and Applications to Constraint Databases.},
year = {1999},
journal = {J. ACM},
author = {{Saugata Basu}}
}
@inproceedings{conf/stoc/Bas02,
title = {Computing the betti numbers of arrangements.},
year = {2002},
booktitle = {STOC},
author = {{Saugata Basu}},
publisher = {ACM},
booktitle = {Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada}
}
@article{journals/dcg/Basu03,
title = {The Combinatorial and Topological Complexity of a Single Cell.},
year = {2003},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu}}
}
@article{journals/dcg/Basu03a,
title = {Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets.},
year = {2003},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu}}
}
@article{journals/jcss/Basu03,
title = {Computing the Betti numbers of arrangements via spectral sequences.},
year = {2003},
journal = {J. Comput. Syst. Sci.},
author = {{Saugata Basu}}
}
@inproceedings{conf/gd/BasuDP04,
title = {On the Realizable Weaving Patterns of Polynomial Curves in R^{3}.},
year = {2004},
booktitle = {GD},
author = {{Saugata Basu} and {Raghavan Dhandapani} and {Richard Pollack}},
publisher = {Springer},
booktitle = {Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004, Revised Selected Papers}
}
@inproceedings{conf/casc/BasuK05,
title = {Computing the Betti Numbers of Arrangements in Practice.},
year = {2005},
booktitle = {CASC},
author = {{Saugata Basu} and {Michael Kettner}},
publisher = {Springer},
booktitle = {Computer Algebra in Scientific Computing, 8th International Workshop, CASC 2005, Kalamata, Greece, September 12-16, 2005, Proceedings}
}
@inproceedings{conf/stoc/Basu05,
title = {Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities.},
year = {2005},
booktitle = {STOC},
author = {{Saugata Basu}},
publisher = {ACM},
booktitle = {Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}
}
@inproceedings{conf/stoc/BasuPR05,
title = {Computing the first Betti number and the connected components of semi-algebraic sets.},
year = {2005},
booktitle = {STOC},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}},
publisher = {ACM},
booktitle = {Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}
}
@article{journals/cc/BasuPR05,
title = {Computing the euler-poincaré characteristics of sign conditions.},
year = {2005},
journal = {Comput. Complex.},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@article{journals/cc/Basu06,
title = {Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities.},
year = {2006},
journal = {Comput. Complex.},
author = {{Saugata Basu}}
}
@article{journals/corr/abs-math-0603248,
title = {Computing the First Betti Numberand Describing the Connected Components of Semi-algebraic Sets},
year = {2006},
journal = {CoRR},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@article{journals/corr/abs-math-0603256,
title = {An asymptotically tight bound on the number of connected components of realizable sign conditions},
year = {2006},
journal = {CoRR},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@article{journals/corr/abs-math-0603262,
title = {Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time},
year = {2006},
journal = {CoRR},
author = {{Saugata Basu}}
}
@article{journals/jsc/Basu06,
title = {Computing the first few Betti numbers of semi-algebraic sets in single exponential time.},
year = {2006},
journal = {J. Symb. Comput.},
author = {{Saugata Basu}}
}
@inproceedings{conf/stoc/Basu07,
title = {Combinatorial complexity in O-minimal geometry.},
year = {2007},
booktitle = {STOC},
author = {{Saugata Basu}},
publisher = {ACM},
booktitle = {Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007}
}
@article{journals/corr/abs-0708-2854,
title = {Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems},
year = {2007},
journal = {CoRR},
author = {{Saugata Basu}}
}
@article{journals/corr/abs-0708-3522,
title = {Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials},
year = {2007},
journal = {CoRR},
author = {{Saugata Basu} and {Dmitrii V. Pasechnik} and {Marie-Françoise Roy}}
}
@article{journals/cc/BasuBGL08,
title = {Polynomials that Sign Represent Parity and Descartes' Rule of Signs.},
year = {2008},
journal = {Comput. Complex.},
author = {{Saugata Basu} and {Nayantara Bhatnagar} and {Parikshit Gopalan} and {Richard J. Lipton}}
}
@article{journals/dcg/Basu08,
title = {On the Number of Topological Types Occurring in a Parameterized Family of Arrangements.},
year = {2008},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu}}
}
@article{journals/dcg/BasuK08,
title = {A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities.},
year = {2008},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Michael Kettner}}
}
@article{journals/dcg/BasuZ08,
title = {On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities.},
year = {2008},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Thierry Zell}}
}
@article{journals/focm/Basu08,
title = {Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time.},
year = {2008},
journal = {Found. Comput. Math.},
author = {{Saugata Basu}}
}
@article{journals/focm/Basu08a,
title = {Errata for Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time.},
year = {2008},
journal = {Found. Comput. Math.},
author = {{Saugata Basu}}
}
@article{journals/focm/BasuPR08,
title = {Computing the First Betti Number of a Semi-Algebraic Set.},
year = {2008},
journal = {Found. Comput. Math.},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@article{journals/combinatorica/BasuPR09,
title = {An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions.},
year = {2009},
journal = {Comb.},
author = {{Saugata Basu} and {Richard Pollack} and {Marie-Françoise Roy}}
}
@article{journals/corr/abs-0902-3304,
title = {A bound on the minimum of a real positive polynomial over the standard simplex},
year = {2009},
journal = {CoRR},
author = {{Saugata Basu} and {Richard Leroy} and {Marie-Françoise Roy}}
}
@article{journals/focm/BasuZ10,
title = {Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda's Theorem.},
year = {2010},
journal = {Found. Comput. Math.},
author = {{Saugata Basu} and {Thierry Zell}}
}
@article{journals/jsc/BasuR10,
title = {Bounding the radii of balls meeting every connected component of semi-algebraic sets.},
year = {2010},
journal = {J. Symb. Comput.},
author = {{Saugata Basu} and {Marie-Françoise Roy}}
}
@article{journals/dcg/BaroneB12,
title = {Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety.},
year = {2012},
journal = {Discret. Comput. Geom.},
author = {{Sal Barone} and {Saugata Basu}}
}
@article{journals/focm/Basu12,
title = {A Complex Analogue of Toda's Theorem.},
year = {2012},
journal = {Found. Comput. Math.},
author = {{Saugata Basu}}
}
@article{journals/corr/BasuP13,
title = {Spectral Sequences, Exact Couples and Persistent Homology of filtrations.},
year = {2013},
journal = {CoRR},
author = {{Saugata Basu} and {Laxmi Parida}}
}
@article{journals/corr/BasuR13,
title = {Bounding the equivariant Betti numbers and computing the generalized Euler-Poincaré characteristic of symmetric semi-algebraic sets.},
year = {2013},
journal = {CoRR},
author = {{Saugata Basu} and {Cordian Riener}}
}
@article{journals/dcg/BasuGV13,
title = {A Helly-Type Theorem for Semi-monotone Sets and Monotone Maps.},
year = {2013},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Andrei Gabrielov} and {Nicolai N. Vorobjov Jr.}}
}
@article{journals/corr/Basu14,
title = {Algorithms in Real Algebraic Geometry: A Survey.},
year = {2014},
journal = {CoRR},
author = {{Saugata Basu}}
}
@article{journals/corr/BasuS14,
title = {Polynomial partitioning on varieties and point-hypersurface incidences in four dimensions.},
year = {2014},
journal = {CoRR},
author = {{Saugata Basu} and {Martín Sombra}}
}
@article{journals/dcg/BasuR14,
title = {Divide and Conquer Roadmap for Algebraic Sets.},
year = {2014},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Marie-Françoise Roy}}
}
@article{journals/focm/BasuRDS14,
title = {A Baby Step-Giant Step Roadmap Algorithm for General Algebraic Sets.},
year = {2014},
journal = {Found. Comput. Math.},
author = {{Saugata Basu} and {Marie-Françoise Roy} and {Mohab Safey El Din} and {Éric Schost}}
}
@inproceedings{conf/recomb/ParidaUYCKB15,
title = {Topological Signatures for Population Admixture.},
year = {2015},
booktitle = {RECOMB},
author = {{Laxmi Parida} and {Filippo Utro} and {Deniz Yörükoglu} and {Anna Paola Carrieri} and {David Kuhn} and {Saugata Basu}},
publisher = {Springer},
booktitle = {Research in Computational Molecular Biology - 19th Annual International Conference, RECOMB 2015, Warsaw, Poland, April 12-15, 2015, Proceedings}
}
@article{journals/corr/BasuR15,
title = {On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities.},
year = {2015},
journal = {CoRR},
author = {{Saugata Basu} and {Cordian Riener}}
}
@article{journals/focm/Basu15,
title = {A Complexity Theory of Constructible Functions and Sheaves.},
year = {2015},
journal = {Found. Comput. Math.},
author = {{Saugata Basu}}
}
@article{journals/bmcsb/PlattBZP16,
title = {Characterizing redescriptions using persistent homology to isolate genetic pathways contributing to pathogenesis.},
year = {2016},
journal = {BMC Syst. Biol.},
author = {{Daniel E. Platt} and {Saugata Basu} and {Pierre A. Zalloua} and {Laxmi Parida}}
}
@article{journals/corr/BasuI16,
title = {Categorical Complexity.},
year = {2016},
journal = {CoRR},
author = {{Saugata Basu} and {M. Umut Isik}}
}
@article{journals/corr/BasuR16a,
title = {Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets.},
year = {2016},
journal = {CoRR},
author = {{Saugata Basu} and {Cordian Riener}}
}
@article{journals/corr/BasuR16b,
title = {On the equivariant Betti numbers of symmetric semi-algebraic sets: vanishing, bounds and algorithms.},
year = {2016},
journal = {CoRR},
author = {{Saugata Basu} and {Cordian Riener}}
}
@article{journals/corr/BasuR16c,
title = {An o-minimal Szemerédi-Trotter theorem.},
year = {2016},
journal = {CoRR},
author = {{Saugata Basu} and {Orit E. Raz}}
}
@article{journals/dcg/BasuS16,
title = {Polynomial Partitioning on Varieties of Codimension Two and Point-Hypersurface Incidences in Four Dimensions.},
year = {2016},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Martín Sombra}}
}
@inproceedings{conf/wabi/BasuUP18,
title = {Essential Simplices in Persistent Homology and Subtle Admixture Detection.},
year = {2018},
booktitle = {WABI},
author = {{Saugata Basu} and {Filippo Utro} and {Laxmi Parida}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {18th International Workshop on Algorithms in Bioinformatics, WABI 2018, August 20-22, 2018, Helsinki, Finland}
}
@article{journals/dcg/BasuR18,
title = {Multi-degree Bounds on the Betti Numbers of Real Varieties and Semi-algebraic Sets and Applications.},
year = {2018},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Anthony Rizzie}}
}
@article{journals/bmcgenomics/Guzman-SaenzHBP19,
title = {Signal enrichment with strain-level resolution in metagenomes using topological data analysis.},
year = {2019},
journal = {BMC Genom.},
author = {{Aldo Guzmán-Sáenz} and {Niina Haiminen} and {Saugata Basu} and {Laxmi Parida}}
}
@inproceedings{conf/alcob/MandalGHBP20,
title = {A Topological Data Analysis Approach on Predicting Phenotypes from Gene Expression Data.},
year = {2020},
booktitle = {AlCoB},
author = {{Sayan Mandal} and {Aldo Guzmán-Sáenz} and {Niina Haiminen} and {Saugata Basu} and {Laxmi Parida}},
publisher = {Springer},
booktitle = {Algorithms for Computational Biology - 7th International Conference, AlCoB 2020, Missoula, MT, USA, April 13-15, 2020, Proceedings.}
}
@inproceedings{conf/focs/BasuC21,
title = {Harmonic Persistent Homology (extended abstract).},
year = {2021},
booktitle = {FOCS},
author = {{Saugata Basu} and {Nathanael Cox}},
publisher = {IEEE},
booktitle = {62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022}
}
@article{journals/corr/abs-2101-07417,
title = {Inferring COVID-19 Biological Pathways from Clinical Phenotypes via Topological Analysis.},
year = {2021},
journal = {CoRR},
author = {{Negin Karisani} and {Daniel E. Platt} and {Saugata Basu} and {Laxmi Parida}}
}
@article{journals/corr/abs-2104-05053,
title = {Hausdorff approximations and volume of tubes of singular algebraic sets.},
year = {2021},
journal = {CoRR},
author = {{Saugata Basu} and {Antonio Lerario}}
}
@inproceedings{conf/focs/BasuKMN22,
title = {Geometry of Secure Two-party Computation.},
year = {2022},
booktitle = {FOCS},
author = {{Saugata Basu} and {Hamidreza Amini Khorasgani} and {Hemanta K. Maji} and {Hai H. Nguyen}},
publisher = {IEEE},
booktitle = {63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022}
}
@article{journals/corr/abs-2208-01450,
title = {Sequents, barcodes, and homology.},
year = {2022},
journal = {CoRR},
author = {{Saugata Basu} and {Negin Karisani} and {Laxmi Parida}}
}
@article{journals/dcg/BasuCP22,
title = {On the Reeb Spaces of Definable Maps.},
year = {2022},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Nathanael Cox} and {Sarah Percival}}
}
@article{journals/focm/BasuR22,
title = {Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets.},
year = {2022},
journal = {Found. Comput. Math.},
author = {{Saugata Basu} and {Cordian Riener}}
}
@article{journals/siaga/BasuN22,
title = {On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate.},
year = {2022},
journal = {SIAM J. Appl. Algebra Geom.},
author = {{Saugata Basu} and {Ali Mohammad Nezhad}}
}
@inproceedings{conf/tcc/BasuKMN23,
title = {Randomized Functions with High Round Complexity.},
year = {2023},
booktitle = {TCC (1)},
author = {{Saugata Basu} and {Hamidreza Amini Khorasgani} and {Hemanta K. Maji} and {Hai H. Nguyen}},
publisher = {Springer},
booktitle = {Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part I}
}
@article{journals/corr/abs-2308-13091,
title = {Quantum Analog of Shannon's Lower Bound Theorem.},
year = {2023},
journal = {CoRR},
author = {{Saugata Basu} and {Laxmi Parida}}
}
@article{journals/siaga/BasuK23,
title = {Persistent Homology of Semialgebraic Sets.},
year = {2023},
month = {September},
journal = {SIAM J. Appl. Algebra Geom.},
author = {{Saugata Basu} and {Negin Karisani}}
}
@article{journals/aam/BasuN24,
title = {On the complexity of analyticity in semi-definite optimization.},
year = {2024},
journal = {Adv. Appl. Math.},
author = {{Saugata Basu} and {Ali Mohammad Nezhad}}
}
@article{journals/siaga/BasuC24,
title = {Harmonic Persistent Homology.},
year = {2024},
month = {March},
journal = {SIAM J. Appl. Algebra Geom.},
author = {{Saugata Basu} and {Nathanael Cox}}
}
@article{journals/dcg/BasuP24,
title = {Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set.},
year = {2024},
month = {September},
journal = {Discret. Comput. Geom.},
author = {{Saugata Basu} and {Sarah Percival}}
}