Nikhil Bansal
University of Michigan, MI·Computer Science
Much of modern computing comes down to optimization: finding the best answer from an enormous number of possibilities, quickly and accurately. Artificial intelligence, scientific computing, scheduling and resource allocation all depend on it.
- Fields
Computer Science
Mathematics & Statistics
- Topics
optimization
interior-point method
discrepancy theory
- Grants
- 2 known grants, through Sep 2029
What they work on
- Determine how many iterations the interior-point method, a standard algorithm for large optimization problems, needs in the worst case, on average and on sparse inputs, to understand its true complexity.
- Develop continuous optimization methods for discrete problems at the frontier of discrepancy minimization, satisfiability and spectral optimization, building on recent breakthroughs.
- Improve approximation algorithms for hard problems through sharper analysis of convex relaxations (easier versions of the problem) and of the practical cutting-plane methods used to solve them.
- Develop algorithms for online and dynamic discrepancy, where objects arrive or change over time, and for prefix discrepancy, where every initial part of a sequence must stay balanced.
- Study beyond-worst-case discrepancy for objects drawn from a probability distribution or perturbed by random noise, aiming at new rounding techniques, fair-division and bin-packing algorithms and faster numerical integration.
More about the research
This research asks what the fastest and most accurate algorithms can achieve, and it develops new mathematical tools to get there. The work draws on computer science, convex geometry, probability, statistics and operations research. Its two projects are closely linked: one on core optimization methods, and one on discrepancy theory, the study of dividing a collection of objects into parts that are as balanced as possible.
Why it matters
Faster and more accurate optimization algorithms underpin artificial intelligence and scientific computing. Better ways to divide items into balanced groups could improve resource allocation, the design of randomized controlled trials, differential privacy (protecting individuals in shared data), scheduling, fair division, bin packing and machine learning, giving software developers more efficient methods with proven performance guarantees.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Patrick Combettes
North Carolina State University, NC·Mathematics & Statistics
Develop a geometric framework unifying stochastic algorithms for convex feasibility, best approximation, convex optimization, fixed-point, variational inequality and monotone inclusion problems, and use it to design new methods.
Sayan Bandyapadhyay
Portland State University, OR·Computer Science
Design polynomial-time approximation algorithms for balanced k-median and k-means clustering, where each cluster must fairly represent every protected group, aiming for constant-factor guarantees like those known for ordinary clustering.
Christian Kroer
Columbia University, NY·Computer Science·Early-career
Develop algorithms for online fair allocation and dynamic markets using online learning and first-order optimization methods, aiming for robustness across different input models rather than a single assumed arrival process.
The school
University of Michigan: 124 labs on PI Pages, $2.1B a year on research, 963 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.