Applications of Discrete Mathematics in Computer Science

UR-CS Participating Faculty: Daniel Stefankovic

Project Description

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:

Bibliography

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.

  1. 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.

  2. Laszlo Babai, Daniel Stefankovic.
    Simultaneous diophantine approximation with excluded primes.
    SODA 2004, p. 1123-1129.

  3. 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.

  4. Marcus Schaefer, Daniel Stefankovic.
    Solvability of graph inequalities.
    SIAM Journal of Discrete Mathematics, 19:3, p. 728-743.

  5. 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.

  6. Daniel Stefankovic.
    Acyclic orientations do not lead to optimal deadlock free packet routing algorithms.
    Information Processing Letters, 73:5-6, p. 221-225, 2000.

  7. 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.

  8. Peter Ruzicka, Daniel Stefankovic.
    On the complexity of multidimensional routing schemes.
    Theoretical Computer Science, 254:2, p. 255-280, 2000.