Advanced Algorithms
We build strong foundations in algorithms with proven performance. Our work tackles challenging problems in global optimization for non-convex tasks, spectral graph theory and exact solutions for complex computational issues. By blending theory with real-world applications, our research contributes to fields like electronic design, fair decision-making, energy-efficient resource allocation and risk assessment. We also address societal challenges, such as ensuring fairness in rideshare services. Across all projects, we rely on rigorous mathematical analysis to ensure our solutions are both theoretically sound and practically useful.
|
James Calvin |
Research Areas: Global optimization, probabilistic analysis of algorithms Global Optimization To solve the pervasive optimization problems in engineering, science and commerce, we are developing “global optimization” algorithms where the objective is to solve optimization problems without getting stuck in local minima. This has applications in the design of fuel-efficient aircraft, the error rate of classification algorithms and financial investing. |
|
|
Ioannis Koutis |
Research Areas: Fast Linear system solvers, spectral graph algorithms, machine learning, data mining Graphs are objects of central interest in data science. A graph can be mapped to linear operators whose spectral properties encode connectivity information, enabling the design of numerical algorithms for various problems on graphs. The practical applicability of such algorithms hinges on the existence of fast solvers for fundamental computational problems, such as systems of linear equations and other generalized regression problems. We have designed such solvers and leveraged them in the design of new graph algorithms based on spectral graph theory for graphs with a prescribed cut structure. As a concrete application, we developed new algorithms for hypergraph partitioning, a key problem in Electronic Design Automation. Our algorithms broke previous records on multiple benchmarks and received the best paper award at the 41st ACM/IEEE ICCAD, in 2022. Multiple well-studied computational problems are conjectured to require exponential time for their solution. Current research aims to develop a detailed understanding of the computational complexity of these problems beyond the classical NP- completeness theory. The design of faster exact algorithms for such problems and their parameterized versions is of key importance in the area. In this context, we pioneered the general method of algebraic fingerprints that reduces various combinatorial problems to monomial detection problems that are, in turn, solved via algebraic algorithms. This research led to breakthrough results for classical algorithmic problems, such as the Hamiltonian cycle problem and single exponential time ,algorithms for problems parameterized by treewidth. Among these breakthrough algorithms, our work on Directed Hamiltonicity and Outbranching problems received the best paper award at the 44th ICALP in 2017. |
|
|
Marvin Nakayama |
Research Areas: Monte Carlo simulation, risk analysis, applied probability, statistics Many disparate fields suffer from uncertainties with detrimental consequences, such as large losses in financial portfolios or failures of critical infrastructure due to natural disasters. Modern society crucially depends on gaining a better understanding of the likelihood and impacts of such calamitous rare events. Our work devises novel approaches for substantially reducing statistical errors in Monte Carlo simulation, a computational technique that can be employed to study risks in decision-making and analytics. One project focuses on designing improved methods for probabilistic safety assessments of nuclear power plants. The work also applies to evaluating the reliability of complex systems such as aircraft navigation computers, package-tracking systems for overnight delivery companies and the dependability of supply chains. |
|
|
Baruch Schieber |
Research Areas: Algorithms, mathematics of artificial intelligence (AI), optimization Graphs are used extensively to model various kinds of networks, such as transportation or social networks. In most real-life applications these networks change over time so their characteristics are changing as well. The goal of dynamic graph algorithms is to compute these characteristics over time as efficiently as possible. The required output can be recomputed from scratch at each time point, however, in many cases, the slow pace of change relative to the size of the network enables much faster computation. One such characteristic is the maximal independent set (MIS) of the graph, which has extensive connections to many fundamental combinatorial optimization problems, such as maximum matching, minimum vertex cover and graph coloring. We developed several dynamic algorithms for computing MIS including the first sublinear amortized update time algorithm for maintaining an MIS in dynamic graphs. Location problems are an important class of combinatorial optimization problems that arise in applications such as choosing facility sites in a supply chain, placing servers in a telecommunication network and clustering data. The underlying distance function in many cases is Euclidean. It is natural to ask whether the Euclidean metrics can be leveraged to obtain more efficient algorithms than the ones known on a general metric space. We considered one such location problem, the classical k-supplier problem and showed that there exists an algorithm for this problem on Euclidean metrics that beats the lower bound on the time required for any such algorithm on a general metric space. |
|
|
Pan Xu |
Research Areas: Artificial intelligence, approximation and randomized algorithm, ridershare and crowdsourcing markets Rideshare platforms, such as Uber and Lyft, have gained increasing popularity in recent years. One of the central tasks facing Uber and Lyft is the matching policy pairing drivers and riders. Recently, it has been reported that drivers cancel riders based on their demographic attributes such as gender, race and disability, either intentionally or unintentionally. In our project, we try to leverage the power of algorithm design to curb discriminative cancellations from drivers to riders and improve the social welfare overall. |
|
