Amitabh Basu Contact information
Mailing Address:   Amitabh Basu
         	   Department of Applied Mathematics and Statistics
         	   Johns Hopkins University
		   Wyman Park Building, Room S438
         	   3400 North Charles Street
         	   Baltimore, MD 21218

Department office: Wyman S438
Phone:             410-516-7582
Email:             basu.amitabh[AT]jhu[DOT]edu


I'm a Professor in the Applied Mathematics and Statistics department, with a secondary appointment in the Computer Science department, at Johns Hopkins University. I obtained my PhD in the ACO program at Carnegie Mellon University, advised by Gerard Cornuejols. My research interests lie in Optimization (with current emphasis on Integer Programming), Discrete and combinatorial geometry, and Convex analysis, and the applications of these tools in Operations Research, Astronomy and Data Science.

Heard while eavesdropping on a mathematician: "These schemes are pointless"
Resume pdf
Professional Service

Area Editor, Mathematics of Operations Research, 2023 -- present.
Associate Editor, SIAM Journal on Optimization, 2023 -- present.
Organizing committee member, SIAM conference on optimization, 2023.
Associate Editor, Mathematical Programming, 2022 -- present.
Editorial board member, MOS-SIAM Series on Optimization, 2021 -- present.
Associate Editor, Discrete Optimization, 2017 -- 2022.
Associate Editor, Mathematics of Operations Research, 2013 -- 2022.
Chair, Local organization committee, Integer Programming and Combinatorial Optimization (IPCO) conference, 2025.
Program Committee, Integer Programming and Combinatorial Optimization (IPCO) conference, 2019, 2020, 2025.
Program Committee, International Symposium on Combinatorial Optimization (ISCO) conference, 2018, 2020, 2022, conference co-chair in 2024.
Vice Chair (Integer and Discrete Optimization), INFORMS Optimization Society, 2015-17.
Chair, Program Committee, Mixed Integer Programming workshop (MIP), 2014.
Program Committee, Mixed Integer Programming workshop (MIP), 2013.
Program Committee, Bay Area Discrete Math Day (BADMath), 2012-2013.
Chair, Local organization committee, Mixed Integer Programming workshop (MIP), 2012.
Teaching

Current Courses

AMS 553.665: Introduction to Convexity
AMS 553.766: Combinatorial Optimization

Past Courses

Johns Hopkins U.

AMS 553.465/665: Introduction to Convexity (Fall 2016, 2017, 2018, 2022, 2023, 2024, Spring 2024)
AMS 553.766: Combinatorial Optimization (Fall 2013, 2014, 2015, Spring 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024)
AMS 553.761: Nonlinear Optimization I (Fall 2018, 2019, 2020, 2022)
AMS 553.472/672: Graph Theory (Spring 2014, 2015, 2016)

UC Davis

MAT 25 (Spring 2013)
MAT 17B (Fall 2011, Spring 2012, Fall 2012)
MAT 165 (Fall 2012)
MAT 16A (Spring 2012)
MAT 16B (Spring 2011)
MAT 16C (Spring 2011)

In the 2010-2011 session, I led an RFG on Applications of Convex Geometry, as part of the NSF funded VIGRE program of the Department of Mathematics. Some lecture notes from the Fall session. The Winter quarter activities are recorded here. The Spring activities will be updated on this page.

Carnegie Mellon

Advanced Integer Programming (Spring 2010)
Research Papers

Preprints/Papers Under Review

On the power of graph neural networks and the role of the activation function, submitted (with S. Khalife)

Journal Articles and Refereed Conference Proceedings

Learning cut generating functions for integer programming, (with H. Cheng), to appear in Neural Information Processing Systems (NeurIPS), 2024.
Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut, (with H. Cheng, S. Khalife and B. Fiedorowicz), to appear in Neural Information Processing Systems (NeurIPS), 2024.
A universal transfer theorem for convex optimization algorithms using inexact first-order oracles, (with P. Kerger, M. Molinaro, H. Jiang), Proceedings of the International Conference on Machine Learning (ICML), 2024.
Information complexity of mixed-integer convex optimization, (with H. Jiang, P. Kerger, M. Molinaro), to appear in Mathematical Programming. A preliminary version appeared in Proceedings of IPCO 2023, Lecture Notes in Computer Science, vol. 12904, pp. 1--13.
Neural networks with linear threshold activations: structure and algorithms, (with S. Khalife and H. Cheng), Mathematical Programming, vol. 206, 2024, pp. 333--356. A preliminary version appeared in Proceedings of IPCO 2022, Lecture Notes in Computer Science, vol. 13265, pp. 347--360.
Fast Globally Optimal Catalog Matching using MIQCP, (with J. Feitelberg and T. Budavari), The Astronomical Journal, vol. 166(4), October 2023.
Complexity of optimizing over the integers, Mathematical Programming, vol. 200, 2023, pp. 739--780.
Complexity of branch-and-bound and cutting planes in mixed-integer optimization, (with M. Conforti, M. Di Summa and H. Jiang), Mathematical Programming, vol. 198 (1), 2023, pp. 787--810.
Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II, (with M. Conforti, M. Di Summa and H. Jiang), Combinatorica, vol. 42, 2022, pp. 971--996. A preliminary version appears in Proceedings of IPCO 2021, Lecture Notes in Computer Science, vol. 12707, pp. 383--398.
Two-halfspace closure, (with H. Jiang), Mathematical Programming, vol. 197, 2023, pp. 411--426 (short communication).
Distance-based Positive and Unlabeled Learning for Ranking, (with H. S. Helm, A. Athreya, Y. Park, J. T. Vogelstein, M. Winding, M. Zlatic, A. Cardona, P. Bourke, J. Larson, C. White, C. E. Priebe), Pattern Recognition, vol. 134, Feb 2023, article id 109085. DOI link.
Neural networks with linear threshold activations: structure and algorithms, (with S. Khalife), Proceedings of IPCO 2022, Lecture Notes in Computer Science, vol. 13265, pp. 347--360.
Globally optimal and scalable N-way matching of astronomy catalogs, (with T. Nguyen, T. Budavari), The Astronomical Journal, vol. 163(6), article id. 296, May 2022.
Enumerating integer points in polytopes with bounded subdeterminants, (with H. Jiang), SIAM J. on Discrete Mathematics, vol. 36(1), 2022, pp. 449--460.
Towards Lower Bounds on the Depth of ReLU Neural Networks, (with C. Hertrich, M. Di Summa, M. Skutella), Proceedings of Advances in Neural Information Processing Systems (NeurIPS) 2021.
Split cuts in the plane, (with M. Conforti, M. Di Summa and H. Jiang), SIAM Journal on Optimization, vol. 31(1), 2021, pp. 331--347.
Admissibility of solution estimators for stochastic optimization, (with T. Nguyen and A. Sun), SIAM Journal on Mathematics of Data Science, vol. 3(1), 2021, pp. 31--51.
Mixed-integer bilevel representability, (with C. Ryan and S. Sriram), Mathematical Programming, vol. 185, 2021, pp. 163--197.
Optimal Probabilistic Catalogue Matching for Radio Sources, (with D. Fan, T. Budavari, R. Norris), Monthly Notices of the Royal Astronomical Society, vol. 498(1), October 2020, pp. 565--573.
An extreme function which is nonnegative and discontinuous everywhere, (with M. Conforti and M. Di Summa), Mathematical Programming, vol. 179, 2020, pp. 447--453 (short communication).
The structure of the infinite models in integer programming, (with M. Conforti, M. Di Summa, and J. Paat), Mathematics of Operations Research, vol. 44(4), 2019, pp. 1412--1430. A preliminary version appears in Proceedings of IPCO 2017, Lectures Notes in Computer Science, vol. 10328, pp. 63--74.
Mixed-integer linear representability, disjunctions, and variable elimination -- modeling implications, (with K. Martin, C. Ryan, and G. Wang), Mathematics of Operations Research, vol. 44(4), 2019, pp. 1264--1285. A preliminary version appears in Proceedings of IPCO 2017, Lectures Notes in Computer Science, vol. 10328, pp. 75--85.
Optimal cutting planes from the group relaxations, (with M. Conforti, M. Di Summa and G. Zambelli), Mathematics of Operations Research, vol. 44(4), 2019, pp. 1208--1220.
Robust registration of astronomy catalogs with applications to the Hubble Space Telescope, (with F. Tian, T. Budavari, S. Lubow, and R. White), The Astronomical Journal, vol. 158(5), article id. 191, Oct. 2019.
Non-unique lifting of integer variables in minimal inequalities, (with S. Dey and J. Paat), SIAM Journal on Discrete Mathematics, vol. 33(2), 2019, pp. 755--783.
Can cut generating functions be good and efficient?, (with S. Sriram), SIAM Journal on Optimization, vol. 29(2), 2019, pp. 1190 -- 1210. Random Dense Instances.
Probabilistic cross-identification of multiple catalogs in crowded fields, (with X. Shi and T. Budavari), The Astrophysical Journal, vol. 870(1), article id 51, Jan. 2019.
Approximation of minimal functions by extreme functions, (with T. Lebair), SIAM Journal on Optimization, vol. 28(3), 2018, pp. 2518 -- 2540.
Sparse coding and autoencoders, (with A. Rangamani, A. Mukherjee, T. Ganapathy, A. Arora, S. Chin, and T. D. Tran), Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2018.
Understanding Deep Neural Networks with ReLUs, (with R. Arora, P. Mianjy, and A. Mukherjee), Proceedings of the International Conference on Learning Representations (ICLR) 2018.
Extreme Functions with an Arbitrary Number of Slopes, (with M. Conforti, M. Di Summa and J. Paat), Mathematical Programming, vol. 172(1), 2018, pp. 303 -- 327. A subset of these results appeared in Proceedings of IPCO 2016, Lecture Notes in Computer Science, vol. 9682, pp. 190--201.
Minimal cut-generating functions are nearly extreme, (with M. Molinaro and R. Hildebrand), Mathematical Programming, vol. 172(1--2), 2018, pp. 329 -- 349. A subset of these results appeared in Proceedings of IPCO 2016, Lecture Notes in Computer Science, vol. 9682, pp. 202--213.
Approximation of corner polyhedra with families of intersection cuts, (with G. Averkov, J. Paat), SIAM Journal on Optimization, vol. 28(1), 2018, pp. 904--929. A subset of these results appeared in Proceedings of IPCO 2017, Lectures Notes in Computer Science, vol. 10328, pp. 51--62.
Optimality certificates for convex minimization and Helly numbers, (with M. Conforti, G. Cornuejols, R. Weismantel, S. Weltge), Operation Research Letters, vol 45(6), 2017, pp. 671--674.
Centerpoints: A link between optimization and convex geometry, (with T. Oertel), SIAM Journal on Optimization, vol. 27(2), 2017, pp. 866--889. A subset of these results appeared in Proceedings of IPCO 2016, Lecture Notes in Computer Science, vol. 9682, pp. 14--25.
Strong duality and sensitivity analysis in semi-infinite linear programming, (with K. Martin and C. Ryan), Mathematical Programming, vol. 161(1), 2017, pp. 451--485. The article is available online at Springer via http://dx.doi.org/10.1007/s10107-016-1018-2
Equivariant Perturbations for Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2, (with R. Hildebrand, M. Koeppe), Mathematical Programming, vol. 163(1), 2017, pp. 301--358. The article is available online at Springer via http://dx.doi.org/10.1007/s10107-016-1064-9
Galaxy Redshifts from Discrete Optimization of Correlation Functions, (with B. Lee, T. Budavari and M. Rahman), The Astronomical Journal, vol. 152(6), article id 155, Nov. 2016.
Probabilistic Cross-Identification in Crowded Fields as an Assignment Problem, (with T. Budavari), The Astronomical Journal, vol. 152(4), article id 86, Sept. 2016.
Computing approximate PSD factorizations, (with M.Dinitz and X. Li), Proceedings of APPROX-RANDOM 2016, Leibniz International Proceedings in Informatics, vol. 60, article id 2.
Light on the infinite group relaxation, (with R. Hildebrand, M. Koeppe), invited survey in 4OR: A quarterly journal of operations research. The final publication appears in two parts: Part I, 4OR, vol. 14(1), March 2016, pp. 1--40, and Part II, 4OR, vol. 14(2), June 2016, pp. 107--131.
Operations that preserve the covering property of the lifting region, (with J. Paat), SIAM Journal on Optimization, vol. 25(4), 2015, pp. 2313--2333. The final publication is available via SIAM at http://dx.doi.org/10.1137/140990413.
Lifting Properties of Maximal Lattice-free Polyhedra, (with G. Averkov), Mathematical Programming, vol. 154(1), 2015, pp. 81-111. The final publication is available at Springer via http://dx.doi.org/10.1007/s10107-015-0865-6.
A geometric approach to cut-generating functions, (with M. Conforti, M. Di Summa), Mathematical Programming, vol.151(1), 2015, pp. 153-189. The final publication is available at Springer via http://dx.doi.org/10.1007/s10107-015-0890-5.
Characterization of the Split Closure via Geometric Lifting, (with M. Molinaro), European Journal of Operational Research, vol. 243(3), 2015, pp. 745-751. The final publication is available via http://dx.doi.org/10.1016/j.ejor.2014.12.018.
Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming, (with K. Martin, C. Ryan), Mathematics of Operations Research, vol. 40(1), 2015, pp. 146-170.
Equivariant Perturbations for Gomory and Johnson's Infinite Group Problem I. The One-Dimensional Case, (with R. Hildebrand, M. Koeppe), Mathematics of Operations Research, vol. 40(1), 2015, pp. 105--129.
On the Unique-lifting Property, (with G. Averkov), Proceedings of IPCO 2014, LNCS 8494, 2014, pp. 76--87.
The Triangle Closure is a Polyhedron, (with R. Hildebrand, M. Koeppe), Mathematical Programming, vol. 145 (1-2), 2014, pp. 19--58.
On Chubanov's method for Linear Programming, (with J. De Loera, M. Junod), INFORMS Journal on Computing, vol. 26(2), 2014, pp. 336--350.
On the sufficiency of finite support duals in semi-infinite linear programming, (with K. Martin, C. Ryan), Operations Research Letters, vol. 42(1), 2014, pp. 16--20.
Equivariant Perturbations for Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two Dimensional Case, (with R. Hildebrand, M. Koeppe), Proceedings of IPCO 2013, LNCS 7801, 2013, pp 62--73.
A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation, (with R. Hildebrand, M. Koeppe, M. Molinaro), SIAM Journal on Optimization, vol. 23(2), 2013, pp. 1021--1040.
Unique lifting of integer variables in minimal inequalities, (with M. Campelo, M. Conforti, G. Cornuejols, G. Zambelli), Mathematical Programming, , vol. 141, 2013, pp. 561--576. DOI: 10.1007/s10107-012-0560-9. A subset of these results appeared in On Lifting Integer Variables in Minimal Inequalities, Proceedings of IPCO 2010, LNCS 6080, 2010, pp. 85--95.
A Counterexample to a Conjecture by Gomory and Johnson, (with M. Conforti, G. Cornuejols and G. Zambelli) Mathematical Programming, vol. 133, 2012, pp. 25--38. DOI: 10.1007/s10107-010-0407-1.
Unique Minimal Liftings for Simplicial Polytopes, (with G. Cornuejols and M. Koeppe), Mathematics of Operations Research vol. 37 (2), 2012, pp. 346--355.
Intersection cuts with Infinite Split Rank, (with G. Cornuejols and F. Margot) Mathematics of Operations Research vol. 37 (1), 2012, pp. 21--40. The published version of the paper has a couple of errors which are corrected here. The ArXiv version linked here does not have these errors.
A Probabilistic Analysis of the Strength of Split and Triangle Closures, (with G. Cornuejols and M. Molinaro) IPCO 2011 version, Proceedings of IPCO 2011, LNCS 6655, 2011, pp. 27--38.
Experiments with two row cuts from degenerate tableaux, (with P. Bonami, G. Cornuejols and F. Margot) INFORMS Journal of Computing vol. 23 (4), 2011, pp. 578--590.
Convex Sets and Minimal Sublinear Functions, (with G. Cornuejols and G. Zambelli) Journal of Convex Analysis, vol. 18(2), 2011, pp. 427--432.
Maximal Lattice-free Convex Sets in Linear Subspaces, (with M. Conforti, G. Cornuejols and G. Zambelli) Mathematics of Operations Research vol. 35 (3), 2010, pp. 704--720.
Minimal Inequalities for an Infinite Relaxation of Integer Programs, (with M. Conforti, G. Cornuejols and G. Zambelli) SIAM Journal on Discrete Mathematics, vol. 24 (1), 2010, pp. 158--168.
On the Relative Strength of Split, Triangle and Quadrilateral Cuts, (with P. Bonami, G. Cornuejols and F. Margot) Mathematical Programming,, vol. 126 (2), 2011, pp. 281-314. Preliminary version in Proc. ACM-SIAM SODA, New York, January 2009.
Geometric Algorithms for Optimal Airspace Design and Air Traffic Controller Workload Balancing, (with J.S.B. Mitchell and G. Sabhnani) ACM Journal on Experimental Algorithmics, vol. 14 (2), 2009, pp. 3--28, Preliminary version in Proc. SIAM ALENEX 2008.
Distributed Localization using Noisy Distance and Angle Information, (with J. Gao, J.S.B. Mitchell and G. Sabhnani) Proc. ACM MobiHoc'06, 262-273, Florence, Italy, May, 2006.
Security types preserving compilation, (with G. Barthe and T. Rezk) Computer Languages, Systems and Structures vol. 33 (2), July 2007, pp. 35--59, Extended Abstract in Proc. VMCAI 2004, 2-15.

Other manuscripts and expository notes

Helly systems and certificates in optimization, (with T. Chen, M. Conforti and H. Jiang)
A perspective on human and artificial intelligence
Notes on Lasserre hierarchies, SOS relaxations and pseudo-expectations
An exposition of special relativity without appeal to "constancy of speed of light" hypotheses
Introduction to Convexity
Lower bounds over Boolean inputs for deep neural networks with ReLU gates, (with A. Mukherjee)
Lectures on Modern Approaches to Cutting Planes
Maximal Lattice-free Convex Sets in 3 Dimensions (with Gerard Cornuejols and Francois Margot)
Steiner Point Removal in Graph Metrics (with Anupam Gupta)