Applications of Discrete Mathematics in Computer Science
This project studies applications of discrete mathematics in computer science. The topics include
combinatorics, counting, coding theory, game theory, learning theory, routing, and phylogeny. Examples of questions studied are:
What problems do admit efficient approximate counting algorithms?
Are there good codes that can be tested by looking at a small portion of a codeword (locally testable codes)?
Are there good codes that exhibit large symmetries (e.g., locally testable codes)?
Suppose that we have a family of sets such that their sizes and the sizes of their intersections are restricted
to certain values. How large can such a family be?
Two players are playing a game. There are only three possible outcomes of the game: either both players lose, or
one of the players wins. Can we find Nash equilibria for such games efficiently?
This is a list of selected journal (except when the work has not yet
appeared in journal/book form) papers, from or related to this project, by
University of Rochester authors.
Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang.
Phase transition for Glauber dynamics for independent sets on regular trees.
22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011).
Qi Ge, Daniel Stefankovic.
A graph polynomial for independent sets of bipartite graphs.
30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), pp. 240–
Qi Ge and Daniel Stefankovic.
The complexity of counting eulerian tours in 4-regular graphs.
9th Latin American Theoretical Informatics Symposium (LATIN 2010), pp. 638–649, 2010.
Satyaki Mahalanabis and Daniel Stefankovic.
Approximating L1-distances between mixture distributions using random projections.
6th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2009), pp. 75–84,
Satyaki Mahalanabis, Daniel Stefankovic.
Density estimation in linear time.
21st Annual Conference on Learning Theory (COLT 2008), pp. 503–512, 2008.
Daniel Stefankovic, Santosh Vempala, Eric Vigoda.
Adaptive simulated annealing: A near-optimal connection between sampling and counting.
Journal of the Association for Computing Machinery (JACM) 56:3, 2009.
A preliminary version appeared in FOCS 2007, p. 183-193.
Ivona Bezakova, Daniel Stefankovic, Vijay Vazirani, Eric Vigoda.
Accelerating simulated annealing for the permanent and combinatorial counting problems.
SIAM Journal on Computing 37(5):1429-1454, 2008.
A preliminary version appeared in SODA 2006, pp. 900-907.
Daniel Stefankovic, Eric Vigoda.
Phylogeny of mixture models: robustness of maximum likelihood and nonidentifiable
Journal of Computational Biology 14(2):156–189, 2007.
Daniel Stefankovic, Eric Vigoda.
Pitfalls of heterogeneous processes for phylogenetic reconstruction.
Systematic Biology 56(1):113–124, 2007.
Manu Chhabra, Robert Jacobs, Daniel Stefankovic.
Behavioral shaping for geometric concepts.
Journal of Machine Learning Research (JMLR) 8:1835–1865, 2007.
Bruno Codenotti, Daniel Stefankovic.
On the computational complexity of Nash equilibria for (0,1)-bimatrix games.
Information Processing Letters, 94:3, p. 145-150, 2005.
Marcus Schaefer, Daniel Stefankovic.
Solvability of graph inequalities.
SIAM Journal of Discrete Mathematics, 19:3, p. 728-743, 2005.
Laszlo Babai, Daniel Stefankovic.
Simultaneous diophantine approximation with excluded primes.
SODA 2004, p. 1123-1129.
Laszlo Babai, Amir Shpilka, Daniel Stefankovic.
Locally testable cyclic codes.
IEEE Transactions on Information Theory, 51(8), p. 2849-2858, 2005.
A preliminary version appeared in FOCS 2003, p. 116-125.
Laszlo Babai, Peter Frankl, Samuel Kutin, Daniel Stefankovic.
Set systems with restricted intersections modulo prime powers.
Journal of Combinatorial Theory A, 95:1, p. 39-73, 2001.
Acyclic orientations do not lead to optimal deadlock free packet routing algorithms.
Information Processing Letters, 73:5-6, p. 221-225, 2000.
Rastislav Kralovic, Peter Ruzicka, Daniel Stefankovic.
The complexity of shortest path and dilation bounded interval routing.
Theoretical Computer Science, 234:1-2, p. 85-107, 2000,
A preliminary version appeared at Europar 97, LNCS 1300, pp. 258-265.
Peter Ruzicka, Daniel Stefankovic.
On the complexity of multidimensional routing schemes.
Theoretical Computer Science, 254:2, p. 255-280, 2000.