This project studies applications of discrete mathematics in computer science. The topics include
combinatorics, coding theory, game theory, and routing. Examples of questions studied are:
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 boh 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.
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.
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.
Marcus Schaefer, Daniel Stefankovic.
Solvability of graph inequalities. SIAM Journal of Discrete Mathematics, 19:3, p. 728-743.
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.
Daniel Stefankovic.
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.