CUNY Queens College & CUNY Graduate Center

Science Building A202

65-30 Kissena Blvd, Flushing, NY 11367

Email: firstname.lastname@qc.cuny.edu

Prospective Students: I am currently not accepting Ph.D. students via the CUNY Graduate Center. If you have a strong background in mathematics, algorithms or theoretical machine learning, please contact me directly with your CV.

Short Bio: I received my Ph.D. from the Applied Mathematics and Statistics at the Stony Brook University, New York. My advisors were Joe Mitchell and David Gu. From 2013-2016 I was a researcher at the Max-Planck Institute for Informatics in Germany, in the Algorithms and Complexity group headed by Kurt Mehlhorn. I received my Bachelors in Mathematics (B.Math.) from the Indian Statistical Institute, Bangalore, India.

Research Interests:

- Algorithms - sorting, searching, binary search trees, succinct data structures and variants of Bloom filters, graph problems, I/O efficient algorithms, lower bounds.
- Computational geometry and algorithms for geometric databases.
- Theoretical machine learning - removing noisy labels, generalization performance.
- Conformal geometry, Teichmuller theory, and harmonic measure.

I hosted the Fall Workshop on Computational Geometry (FWCG) in October 2018. Here is the webpage.

I organize the Computer Science Seminar, Q4C (Queens College CS Colloquium)

My research is supported thanks to the following sponsors.

- National Science Foundation - AF:Small: RUI: Towards resolving the dynamic optimality conjecture. Award ID: 1910873.
- National Science Foundation CRII: AF: RUI: Faster and Cache-Efficient Similarity Filters and Searches for Big Data (Award Id : 1755791).
- CUNY Collaborative Open Educational Resources in STEM (COERS) Program: Project-based pedagogical approach in introductory C++ courses. Co-PI (along with Daniel Garbin and Kwang Hyun Kim).
- PSC CUNY Cycles 48 and 49 award (type B).

Reverse-chronologically ordered. Authors are ordered alphabetically by convention in theory. Uses of the files linked below are subject to copyrights of respective publishers. Please check before use.

Peer-Reviewed Conferences

- New!! M. Goswami, R. Jacob

On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting

Proc. Of the 27th International Conference on Approximation Algorithms for Combinatorial Optimization (APPROX), August 2024 - M. Goswami, R. Jacob

An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio

Proc. Of the 15th Innovations in Theoretical Computer Science (ITCS), January 2024 - S. Zheng, Y. Zhang, L. Pang, W. Lyu, M. Goswami, A. Schneider, Y. Nevmyvaka, H. Ling, C. Chen

On the Existence of a Trojaned Twin Model

BANDS Workshop at the 11th International Conference on Learning Representations (ICLR), May 2023 - J. Yao, Y. Zhang, S. Zheng, M. Goswami, P. Prasanna, C. Chen

Learning to Segment from Noisy Annotations: A Spatial Correction Approach

The 11th International Conference on Learning Representations (ICLR), May 2023 - Omrit Filtser, Mayank Goswami, Joseph Mitchell, Valentin Polishchuk

On Flipping the Frechet Distance

Proc. of the 14th Innovations in Theoretical Computer Science (ITCS), January 2023 - P. Cesaretti, M.N. Bhat, M. Goswami and P. Pandey

Distance and Time Sensitive Filters for Similarity Search in Trajectory Datasets

Proc. of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS 23), January 2023 - J. Gao, M. Goswami, Karthik C. S., M.T. Tsai, S.Y. Tsai, H.T. Yang

Obtaining Approximately Optimal and Diverse Solutions via Dispersion

Proceedings of the 15th Latin American Theoretical Informatics Symposium (LATIN), November 2022 - D. Deingeniis, X. Zhou, W.M. Wong, Y. Nomura, M. Goswami

The Impact of Maternal PTSD and Child Temperament on Child Behavioral Problems: An Interpretable Machine Learning Approach

Presented at the 38th Annual Meeting of the International Society for Traumatic Stress Studies (ISTSS), November, 2022 - Y. Zhang, W. Zhang, S. Bald, V.P. Pingali, C. Chen, M. Goswami

Stability of SGD: Tightness Analysis and Improved Bounds

Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI) August 2022 - W. Zhang, Y. Zhang, X. Hu, M. Goswami, C. Chen, D. Metaxas

A Manifold View of Adversarial Risk

Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022) - S. Zheng, Y. Zhang, H. Wagner, M. Goswami, C. Chen

Topological Detection of Trojaned Neural Networks

Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS'21), December 2021. - S. Zheng, P. Wu, Y. Zhang, M. Goswami, C. Chen, D. Metaxas

Learning with Feature-Dependent Label Noise: A Progressive Approach

Proc. of the 9th International Conference of Learning Representations (ICLR), 2021. (Spotlight). - P. Wu, S. Zheng, M. Goswami, C. Chen, D. Metaxas

A Topological Filter for Learning with Label Noise

Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS'20), December 2020. - M. Goswami, R. Jacob, R. Pagh

On the I/O-Complexity of the k-nearest neighbors problem

Proc. of the 2020 ACM SIGMOD/PODS (Principles of Database Systems) Conference (PODS'20), June 2020. - S. Zheng, M. Goswami, P. Wu, A. Goswami, C. Chen, D. Metaxas

Error-Bounded Correction of Noisy Labels

Proc. of the 37th International Conference on Machine Learning (ICML'20), July 2020. - E. Arkin, R. Das, J. Gao, M. Goswami, J.S.B. Mitchell, V. Polishchuk, C. Toth

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Proc. of the European Symposium on Algorithms (ESA'20), July 2020. - M. Bender, M. Goswami, D. Mededovic, P. Montes, K. Tsichlas

Batched Predecessor and Sorting with Size-Priced Information in External Memory

Proc. of the 14th Latin American Theoretical Informatics Symposium (LATIN'20), June 2020. - P. Charlemsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak

Multi-finger binary search trees

29th International Symposium on Algorithms and Computation (ISAAC), December 2018. - M. Astefanoaei, P. Cesaretti, P. Katsikouli, M. Goswami, R. Sarkar

Multi-resolution sketches and locality sensitive hashing for fast trajectory processing

Proceedings of the 26th International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2018). - M. A. Bender, M. Farach-Colton, M. Goswami, R. Johnson, S. McCauley, S. Singh

Bloom Filters, Adaptivity and the Dictionary Problem

Proc. of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 2018. - M. Goswami, D. Medjedovic, E. Mekic, P. Pandey

Buffered Count-Min Sketch on SSD: Theory and Experiments

Proc. of the 26th European Symposium on Algorithms (ESA), August 2018. - K.S. Liu, Tyler Mayer, H.T. Yang, E. Arkin, J. Gao, M. Goswami, M.P. Johnson, N. Kumar, S. Lin

Joint Sensing Duty Cycle Scheduling For Heterogenous Coverage Guarantee

Proc. of the 36th Annual IEEE Conference on Computer Communications 2017 (INFOCOMM'17). - M. Goswami, R. Pagh, F. Silvestri, J. Sivertsen

Distance Sensitive Bloom Filters without False Negatives

Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January, 2017. - P. Afshani, M. Bender, M. Farach-Colton, J. Fineman, M. Goswami, M.T. Tsai

Cross Referencing and the Limits of Write Optimization

Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January, 2017. - P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak

Pattern-Avoiding Access in Binary Search Trees

Symposium on Foundations of Computer Science (FOCS'15), October 2015. - J. Gao, M. Goswami

Medial Axis Based Routing has Constant Load Balancing Factor

European Symposium on Algorithms (ESA'15), September 2015. - P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak

Self-Adjusting Binary Search Trees: What Makes Them Tick?

European Symposium on Algorithms (ESA'15), September 2015. - M. Goswami, S. Li, J. Weng, J. Gao, X. Gu, E. Saucan

Space Filling Curves for 3D Sensor Networks with Complex Topologys

Proc. of the 27th Canadian Conference on Computational Geometry (CCCG'15), August 2015. - P.Charlemsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak

Greedy is an almost optimal deque

Proc. of the Algorithms and Data Structures Symposium (WADS'15), August, 2015. - M. Goswami, X. Gu, V. Pingali, G. Telang

Computing Teichmüller Maps between Polygons

Proc. of the 31st International Symposium on Computational Geometry (SoCG'15), June, 2015. Invited to Journal of Computational Geometry (SoCG15 special issue). - M. Goswami, A. Grønlund, K.G. Larsen, R. Pagh

Approximate Range Emptiness in Constant Time and Optimal Space

Proc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), January, 2015. - A. Bishnu, S. Desai, A. Ghosh, M. Goswami, S. Paul

Uniformity of point samples in metric spaces using gap ratio

Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC'15), May 2015. - M. Bender, M. Farach-Colton, M. Goswami, D. Medjedovic, P. Montes, M.T. Tsai

The Batched Predecessor Problem in External Memory

Proc. of the European Symposium on Algorithms (ESA'14), September, 2014. - M. Goswami, C.C. Ni, X. Ban, V. Pingali, J. Gao, X. Gu

Load Balanced Short Path Routing in Large-Scale Wireless Networks Using Area-Preserving Maps

proc. of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'14), August, 2014. - W. Zeng, M. Goswami, X. Gu, F. Luo

Geometric Registration Based on Distortion Estimation

Proc. of the International Conference on Computer Vision (ICCV'13), December, 2013. - X. Ban, M. Goswami, W. Zeng, X. Gu, J. Gao

Topology Dependent Space Filling Curves for Sensor Networks and Applications

Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. - R. Shi, M. Goswami, J. Gao, X. Gu

Is Random Walk Truly Memoryless - Traffic analysis and Source Location Privacy Under Random Walk

Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. - R. Jiang, X. Ban, M. Goswami, W. Zeng, J. Gao, X. Gu

Exploration of Path Space using Sensor Network Geometry

Proc. of the 10th International Symposium on Information Processing in Sensor Networks (IPSN), 49-60, April, 2011.

Journal

- A. Bishnu, S. Desai, A. Ghosh, M. Goswami, S. Paul

Uniformity of Point Samples in Metric Spaces Using Gap Ratio

SIAM J. Discret. Math. 31(3): 2138-2171 (2017). - W. Zhang, Y. Zhang, X. Hu, Y. Yao, M. Goswami, C. Chen, D. Metaxas

Manifold-driven decomposition for adversarial robustness

Frontiers Comput. Sci. 5 (2023). - O. Flitser, M. Goswami, J.S.B. Mitchell, V. Polishchuk

On Flipping the Fréchet Distance

Algorithmica (2024). - M. Goswami, X. Gu, V. Pingali, G. Telang

Computing Teichmüller Maps between Polygons

Journal of Foundations of Computational Mathematics (JoFOCM).

Workshops

- Omrit Filtser, Mayank Goswami, Joseph S.B. Mitchell and Valentin Polishchuk

On Flipping the Frechet Distance

30th Annual Fall Workshop on Computational Geometry (FWCG 2022), October, 2022 - Madhav Narayn Bhat, Paul Cesaretti, Mayank Goswami and Prashant Pandey

Distance and Time Sensitive Filters for Similarity Search in Trajectory Datasets

30th Annual Fall Workshop on Computational Geometry (FWCG 2022), October, 2022 - Jie Gao, Mayank Goswami, Karthik C.S., Meng-Tsung Tsai, Shih-Yu Tsai and Hao-Tsung Yang

Obtaining Approximately Optimal and Diverse Solutions via Dispersion

30th Annual Fall Workshop on Computational Geometry (FWCG 2022), October, 2022 - M. Astefanoaei, P. Katsikouli, M. Goswami, R. Sarkar

Lightweight Sketches for Mining Trajectory Data

The 27th Fall Workshop on Computational Geometry (FWCG), October 2017. - K.S. Liu, T. Mayer, H.T. Yang, E. Arkin, J. Gao, M. Goswami, M.P. Johnson, N. Kumar, S. Lin

Joint Sensing Duty Cycle Scheduling for Heterogeneous Coverage Guarantee

The 26th Fall Workshop on Computational Geometry (FWCG), October 2016. - E. Arkin, P. Brass, R. Das, J. Gao, M. Goswami, J.S.B. Mitchell, V. Polishchuk, C. D. Toth

Optimal Cutting of a Polygon by Lasers

The 26th Fall Workshop on Computational Geometry (FWCG), October 2016. - M. Bender, M. Goswami, D. Medjedovic, P. Arango

The I/O complexity of sorting with two key lengths

Workshop on Massive Data Algorithmics (MASSIVE), 2013.

- On the I/O-Complexity of the K-Nearest Neighbors Problem, Principles of Database Systems (PODS 2020).
- Recent Progress on the Dynamic Optimality Conjecture, NYC Discrete Geometry Seminar, April 2019.
- Multi-finger binary search trees, International Symposium on Algorithms and Computation (ISAAC), Jiaoxi, Taiwan, December 2018.
- On Clairvoyance in Binary Search Trees: Recent Progress on the Dynamic Optimality Conjecture, University of Padova, Italy, September 2018.
- Distance-sensitive Bloom Filters, University of Edinburgh, August 2017.
- Load Balanced Routing using area-preserving maps and medial axis, Courant Geometry Seminar, New York University, November 2016.
- Computing Teichmuller Maps, University of Washington at Seattle, and City University of New York, October 2015.
- Medial axis based routing has constant load balancing factor, European Symposium on Algorithms, Patras (ESA'15).
- Tight lower bounds for approximate range emptiness, Summer School on Lower Bounds, Prague, June 2015.
- Computing Teichmuller Maps between Polygons, Symposium on Computational Geometry, Eindhoven (SoCG'15).
- Approximate Range Emptiness in Constant Time and Optimal Space, Symposium on Discrete Algorithms, San Diego (SODA'15).
- Load Balancing Using Area-Preserving Maps, International Symposium on Mobile Ad Hoc Networking and Computing, Philadelphia (MobiHoc'14).
- Computing Teichmuller Maps between Polygons, Courant Geometry Seminar, New York University, September 2014.
- Approximate Range Emptiness in Constant Time and Optimal Space, CG Group (organized by Joe Mitchell), Stony Brook University, August 2014.
- Computing Teichmuller maps and connections to Tropical Geometry, Oberseminar (organized by Hannah Markwig), Department of Mathematics at University of Saarland, July 2014.
- Geometric Registration Based on Distortion Estimation, International Conference on Computer Vision, Sydney (ICCV'13).
- The I/O complexity of sorting with two key lengths, Max-Planck Institute for Informatics, October 2013.
- Topology Dependent Space Filling Curves for Sensor Networks and Applications, International Conference on Computer Communications, Turin, Italy (INFOCOM'13).
- Is Random Walk Truly Memoryless - Traffic analysis and Source Location Privacy Under Random Walk, International Conference on Computer Communications, Turin, Italy (INFOCOM'13).

- Paul Cesaretti (Spring 2018-present)
- Rakesh Ravindran (Fall 2018-present)
- Sammy Bald (Fall 2018-present)
- Xinglong Zhou (Fall 2020-present)
- GiBeom Park (Fall 2023-present)

- Spring 2021 - Algorithms for Big Data (381/780), Design and Analysis of Algorithms (323/700).
- Fall 2020 - Algorithms for Big Data (381/780), Design and Analysis of Algorithms (323/700), Queens College, and Algorithms for Big Data (80100), Graduate Center.
- Fall 2019 - Algorithms for Big Data (381/780.
- Spring 2019 - Algorithms for Big Data (381/780), Design and Analysis of Algorithms (323/700), Queens College, and Analysis of alogrithms (70010), Graduate Center.
- Fall 2018 - Algorithms for Big Data (381/780), Design and Analysis of Algorithms (323/700).
- Spring 2018 - Algorithms for Big Data (381/780), Design and Analysis of Algorithms (323/700).
- Fall 2017 - Discrete Structures (220), Design and Analysis of Algorithms (323/700).
- Spring 2017 - Discrete Structures (220), Design and Analysis of Algorithms (323/700), Approximation Algorithms (381/780), Queens College, and Modern Approximation Algorithms (83020), Graduate Center.
- Fall 2016 - Discrete Structures (220), Queens College, CUNY. Approximation Algorithms (381/780)
- Approximation Algorithms, Fall 2015, Max-Planck Institute for Informatics.
- Efficient Data Structures, Summer 2014, Max-Planck Institute for Informatics.
- Applied Calculus, Fall 2008, Spring 2009, Stony Brook University.