Kirk Pruhs
University of Pittsburgh, PA·Computer Science
Both of these projects sit in algorithm design: the study of what can be computed efficiently and how. One asks how to turn a class of mathematical existence proofs into actual algorithms that find the objects those proofs promise.
- Fields
Computer Science
Mathematics & Statistics
- Topics
algorithms
computational topology
Sperner's lemma
- Grants
- 2 known grants, through Jul 2029
What they work on
- Develop combinatorial surrogates, graph-theoretic and local expansion conditions, that imply the high topological connectivity needed by topological fixed-point proofs but can be verified by algorithm researchers without topology training.
- Design a constructive version of Sperner's lemma: a polynomial-time algorithm that, perhaps under mild extra preconditions, actually finds the substructure the lemma guarantees exists.
- Build efficient algorithms for specific network substructure problems that currently have only topological existence proofs, using these cases to indicate how Sperner's lemma should be strengthened.
- Develop relational algorithms for basic geometric problems that underlie common machine learning tasks, so they can serve as building blocks for more complex relational learning algorithms.
- Design relational algorithms for standard machine learning problems that run directly on multiple database tables and avoid expensive join operations, matching the standard algorithms' guarantees where possible.
- Determine the limits of the relational model by identifying problems for which no efficient relational algorithm exists, and establish which standard algorithmic design and analysis techniques transfer to this setting.
More about the research
The other asks how to run machine learning directly on data that is spread across many database tables, without first merging them. In each case the common theme is that a problem known to be solvable in principle can still be impractical, and the work is to close that gap.
Why it matters
Turning topological existence proofs into algorithms would give practical methods for problems that currently have only guarantees of solvability, including connectivity in power grids, robustness of supply chains and reliability of communication networks. Relational algorithms would let organizations analyze data in the databases where it already lives, avoiding costly table joins and making machine learning on business and scientific databases cheaper and faster.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
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.
Shaddin Dughmi
University of Southern California, CA·Computer Science
Identify algorithmic recipes for optimal supervised learning by treating classification as bipartite matching on the one-inclusion graph, a structure linking possible labelings of data.
Jingru Zhang
Cleveland State University, OH·Computer Science·Early-career
Develop efficient algorithms for fault-tolerant facility location, which places facilities so demand is still served if some facilities fail, with uncertain demand data.
The school
University of Pittsburgh: 83 labs on PI Pages, $1.5B a year on research, 403 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.