Short Bio: I received my Ph.D. from the Applied
Mathematics and Statistics at the Stony Brook University, New York (CGPA: 3.99/4). My advisors were Joe Mitchell and David Gu. From 20132016 I was a researcher at the MaxPlanck 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.
If you are are a prospective student who wants to enjoy five years solving cool and interesting algorithmic problems (in New York City), send me an email, and check out the graduate program at CUNY Graduate Center.
Research Interests
I am interested in algorithms and mathematical techniques for
handling large sets of data that are either 1)
centralized, 2) distributed or 3) visual.
Centralized data sets  Approximate and adaptive
data structures for databases and the external memory (Disk Access
Model) setting. Apart from developing practical and efficient data structures, I
also enjoy proving lower bounds on problems arising in these
domains.
Distributed data sets  Networks and distributed algorithms for sensor networks
and social networks. The main problems I have studied here are distributed
load balancing in wireless networks, secure communication protocols, efficient data aggregation via
mobile agents and very recently, the topology of social networks. Main
tools here are combinatorics, graph theory and
optimization.
Visual data sets  Computer Graphics and Vision: Computation in shape spaces (moduli
or Teichmuller spaces) and applications to computer vision. Most
of my work here is motivated by surface registration and
matching problems and uses techniques from classical mathematics (differential,
complex and algebraic geometry).
I publish in both theory and applied fields, in conferences ranging
from (FOCS, SODA, SoCG, ESA) to (ICML, INFOCOM, ICCV, IPSN,
MobiHoc). If you want to discuss any problems (possibly, but not
necessarily, relating to my publications below), feel free to
drop me an email.
Grants
 National Science Foundation  AF:Small: RUI: Towards resolving the dynamic optimality conjecture. Award ID: 1910873, $400,000.
 National Science Foundation (MiniCAREER)
CRII: AF: RUI: Faster and CacheEfficient Similarity Filters and Searches for Big Data (Award Id : 1755791). $175,000.
 CUNY Collaborative Open Educational Resources in STEM (COERS) Program:
Projectbased pedagogical approach in introductory C++ courses. $10,000.
CoPI (along with Daniel Garbin and Kwang Hyun Kim).
 PSC CUNY Cycle 49 award (type B). $6000.
 PSC CUNY Cycle 48 award (type B). $6000.
Publications
Reversechronologically ordered. Uses of the files linked below are subject to copyrights of respective publishers. Please check before use.
Conferences
 New!!
M. Goswami, R. Jacob, R. Pagh
On the I/OComplexity of the KNearest Neighbors Problem
Proc. of the 2020 ACM SIGMOD/PODS (Principles of Database Systems) Conference (PODS'20), June 2020
 New!!
S. Zheng, M. Goswami, P. Wu, A. Goswami, C. Chen, D. Metaxas
ErrorBounded Correction of Noisy Labels
Proc. of the 37th International Conference on Machine Learning (ICML'20), July 2020
 New!!
E. Arkin, R. Das, J. Gao, M. Goswami, J.S.B. Mitchell, V. Polishchuk, C.Toth
Cutting Polygons into Small Pieces with Chords: LaserBased Localization
Proc. of the European Symposium on Algorithms (ESA'20), July 2020
 New!!
M. Bender, M. Goswami, D. Mededovic, P. Montes, K. Tsichlas
Batched Predecessor and Sorting with SizePriced 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
Multifinger binary search trees
29th International Symposium on Algorithms and Computation (ISAAC), December 2018

Maria Astefanoaei, Paul Cesaretti, Panagiota Katsikouli, Mayank Goswami and Rik Sarkar
Multiresolution 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. FarachColton, 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 CountMin 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 ACMSIAM Symposium on Discrete Algorithms
(SODA'17), January, 2017.

P. Afshani, M. Bender, M. FarachColton, J. Fineman, M. Goswami, M.T. Tsai
Cross Referencing and the Limits of Write Optimization
Proc. of the 28th Annual ACMSIAM Symposium on Discrete Algorithms
(SODA'17), January, 2017

P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T.Saranurak
PatternAvoiding 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
SelfAdjusting 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 ACMSIAM 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. FarachColton, 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 LargeScale Wireless Networks Using
AreaPreserving 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), 4960, April, 2011
Journal
Workshops

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/OComplexity of the KNearest Neighbors Problem, Principles of Database Systems (PODS 2020)
 Recent Progress on the Dynamic Optimality Conjecture, NYC Discrete Geometry Seminar, April 2019
 Multifinger 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
 Distancesensitive Bloom Filters, University of Edinburgh, August 2017
 Load Balanced Routing using areapreserving 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 AreaPreserving 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,
MaxPlanck 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)
Students
 Paul Cesaretti (Spring 2018present)
 Rakesh Ravindran (Fall 2018present)
 Sammy Bald (Fall 2018present)
 Spring 2018  Algorithms for Big Data (381), Design and Analysis of Algorithms (323).
 Fall 2017  Discrete Structures (220), Design and Analysis of Algorithms (323).
 Spring 2017  Discrete Structures (220), Design and Analysis of Algorithms (323), Approximation Algorithms (381), Queens College, and Modern Approximation Algorithms, Graduate Center, CUNY.
 Fall 2016  Discrete Structures (220), Queens College, CUNY.
Approximation Algorithms
 Approximation Algorithms, Fall 2015, MaxPlanck Institute for Informatics.
 Efficient Data Structures, Summer 2014, MaxPlanck Institute for Informatics.
 Applied Calculus, Fall 2008, Spring 2009, Stony Brook University.
