avgCaseComPapers.html

Average-Case Complexity Papers

(Date Last modified: 07/01/98)

    1. J. Belanger, A. Pavan, and J. Wang. Reductions do not preserve fast convergence rates in average time. Algorithmica, to appear.
    2. J. Belanger and J. Wang. No NP problems averaging over ranking of distributions are harder. Theoretical Computer Science, 181:229-245, 1997.
    3. J. Belanger and J. Wang. Isomorphisms of NP-complete problems on random instances. Proceedings of the 8th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 65-74, 1993.
    4. J. Belanger and J. Wang. Rankable distributions do not provide harder instances than uniform distributions. Proceedings of the 1st International Computing and Combinatorics Conference, vol 959 of Lecture Notes in Computer Science, Springer, pages 410-419, 1995.
    5. J. Belanger and J. Wang. Reductions and convergence rates of average time. Proceedings of the 2nd International Computing and Combinatorics Conference, vol 1090 of Lecture Notes in Computer Science, Springer, pages 300-309, 1996.
    6. S. Ben-David, B. Chor, O. Goldreich, and M. Luby. Theory of average case complexity. Proceedings of the 21st Symposium on Theory of Computing, ACM Press, pages 204-216, 1989.
    7. S. Ben-David, B. Chor, O. Goldreich, and M. Luby. Theory of average case complexity. Journal of Computer and System Sciences, 44:193-219, 1992.
    8. A. Blass and Y. Gurevich. Reduction theory for average-case complexity. Proceedings of the 4th Workshop on Computer Science Logic, vol 533 of Lecture Notes in Computer Science, Springer, pages 17-30, 1991.
    9. A. Blass and Y. Gurevich. Randomizing reductions of search problems. SIAM Journal on Computing, 22:949-975, 1993.
    10. A. Blass and Y. Gurevich. Matrix transformation is complete for the average case. SIAM Journal on Computing, 24:3-29, 1995.
    11. B. Durand. A Random NP-complete problem for inversion of 2D Cellular Automata. Theoretical Computer Science, 148:19--32, 1995. (Also appeared in STACS'95 Lecture Notes in Computer Science, 1995.)
    12. B. Durand, and A-C Fabret. On the complexity of deadlock detection in families of planar nets. Theoretical Computer Science, to appear.
    13. J. -Y. Cai, W. Fuchs, D. Kozen, and Z. Liu. Efficient average-case algorithms for the modular group. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 143-152, 1994.
    14. J. -Y. Cai and A. Selman. Fine Separation of Average Time Complexity Classes. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, vol 1046 of Lecture Notes in Computer Science, Springer, pages 331-343, 1996.
    15. M. Goldmann, P. Grape, and J. Hastad. Average time hierarchies. Information Processing Letters, 49:15-20, 1994.
    16. Y. Gurevich. Complete and incomplete randomized NP problems. Proceedings of the 28th Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 111-117, 1987.
    17. Y. Gurevich. The challenger-solver game: variations on the theme of P =? NP. EATCS Bulletin,
      pages 112-121, 1989.
    18. Y. Gurevich. Matrix decomposition problem is complete for the average case. Proceedings of the 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 802-811, 1990.
    19. Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42:346-398, 1991.
    20. Y. Gurevich. Average case complexity. Proceedings of the 18th International Colloquium on Automata, Languages and Programming, vol 510 of Lecture Notes in Computer Science, Springer, pages 615-628, 1991.
    21. Y. Gurevich. The challenger-solver game: variations on the theme of P =? NP Current Trends in Theoretical Computer Science G. Rozenberg and A. Salomaa eds., World Scientific, pages 245-253, 1993.
    22. Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian path problem. SIAM Journal on Computing, 16:486-502, 1987.
    23. G. Havas and B.S. Majewski. A hard problem that is almost always easy Algorithms and Computation, vol. 1004 of Lecture Notes in Computer Science, pages 216-223, 1995.
    24. R. Impagliazzo. A personal view of average-case complexity. Proceedings of the 10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 134-147, 1995.
    25. R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. Proceedings of the 31th Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 812-821, 1990.
    26. D. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 5:284-299, 1984.
    27. C. Karg. LR(k) testing is average-case complete. Proceedings of the 12th IEEE Conference on Computational Complexity, IEEE Computer Society Press, pages 74-80, 1997.
    28. C. Karg and R. Schuler. Structure in average case complexity. Proceedings of the 6th International Symposium on Algorithms and Computation, vol 1004 of Lecture Notes in Computer Science, Springer, pages 62-71, 1995.
    29. K. Kobayashi. Transformations that preserve malignness of universal distributions. Proceedings of the 1st International Computing and Combinatorics Conference, vol 959 of Lecture Notes in Computer Science, Springer, pages 420-429, 1995.
    30. L. Levin. Average case complete problems. Proceedings of the 16th Symposium on Theory of Computing, ACM Press, page 465, 1984.
    31. L. Levin. Average case complete problems. SIAM Journal on Computing, 15:285-286, 1986.
    32. M. Li and P.Vitányi. Average case complexity under the universal distribution equals worst-case complexity. Information Processing Letters, 42:145-149, 1992.
    33. J. Makowsky and A. Sharell. Average case complexity of SAT for symmetric distribution. Journal of Logic Computation, 5:71-92, 1995.
    34. P. Miltersen. The complexity of malign ensembles. Proceedings of the 6th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 164-171, 1991.
    35. R. Reischuk and C. Schindelhauer. Precise average case complexity. Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science, vol 665 of Lecture Notes in Computer Science, Springer, pages 650-661, 1993.
    36. R. Schuler. Some properties of sets tractable under every polynomial-time computable distribution. Information Processing Letters, 55:179-184, 1995.
    37. R. Schuler. Average polynomial time is hard for exponential time under SN-reductions. Proceedings of the 15th Conference on the Foundations of Software Technology and Theoretical Computer Science,
      vol 1026 of Lecture Notes in Computer Science, Springer, pages 240-247, 1995.
    38. R. Schuler. Truth-table closure and Turing closure of average polynomial time have different measures in EXP. Proceedings of the 11th Conference on Computational Complexity, IEEE Computer Society Press, pages 190-195, 1996.
    39. R. Schuler and O. Watanabe. Towards average-case complexity analysis of NP optimization problems. Proceedings of the 10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 148-159, 1995.
    40. R. Schuler and T. Yamakami. Structural average case complexity. Proceedings of the 12th Conference on the Foundations of Software Technology and Theoretical Computer Science, vol.652 of Lecture Notes in Computer Science, Springer, pages 128-139, 1992.
    41. R. Schuler and T. Yamakami. Sets computable in polynomial time on average. Proceedings of the 1st International Computing and Combinatorics Conference, vol 959 of Lecture Notes in Computer Science, Springer, pages 400-409, 1995.
    42. R. Schuler and T. Yamakami. Structural average case complexity. Journal of Computer and System Sciences, 52:308-327, 1996.
    43. R. Venkatesan and L. Levin. Random instances of a graph coloring problem are hard. Proceedings of the 20th Symposium on Theory of Computing, ACM Press, pages 217-222, 1988.
    44. R. Venkatesan and S. Rajagopalan. Average case intractability of Diophantine and matrix problems. Proceedings of the 24th Symposium on Theory of Computing, ACM Press, pages 632-642, 1992.
    45. J. Wang. Distributional word problems for groups. SIAM Journal on Computing, to appear.
    46. J. Wang. Random instances of bounded string rewriting are hard. Journal of Computing and Information, Vol. 1, No. 1, Special Issue: Proceedings of the 7th International Conference on Computing and Information, pages 11-23, 1995.
    47. J. Wang. Average-case completeness of a word problem for groups. Proceedings of the 27th Symposium on Theory of Computing, ACM Press, pages 325-334, 1995.
    48. J. Wang. Average-case computational complexity theory. (L. Hemaspaandra and A. Selman, eds.), Complexity Theory Retrospective II, Springer. 1996, to appear.
    49. J. Wang. Average-case intractable NP problems. (D.- Z. Du and K.- I. Ko eds.), Advances in Complexity and Algorithms, Kluwer Academic Publishers. 1997, to appear.
    50. J. Wang and J. Belanger. On average-P vs. average-NP. Proceedings of the 7th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 318-326, 1992.
    51. J. Wang and J. Belanger. On average-P vs. average-NP. (K. Ambos-Spies, S. Homer, and U. Schonings eds.), Complexity Theory-Current Research, Cambridge University Press, pages 47-67, 1993.
    52. J. Wang and J. Belanger. Honest iteration schemes of randomizing algorithms. Information Processing Letters, 45:275-278, 1993.
    53. J. Wang and J. Belanger. NP-isomorphism problem with respect to random instances. Journal of Computer and System Sciences, 50:151-164, 1995.
    54. H. Wilf. An O(1) expected time algorithm for the graph coloring problem. Information Processing Letters, 18:119-122, 1984.
    55. T. Yamakami. Polynomial-time samplable distributions. Proceedings of the 21st International Symposium on Mathematical Foundation of Computer Science, Lecture Notes in Computer Science, vol. 1113, pages 566-578, 1996.


    Ph.D. Thesis:


    1. T. Yamakami. Structure of Average Case Hierarchies. Ph.D. Thesis (Advisor: S. Cook), University of Toronto, 1997.
    2. C. Schindelhauer. Average- und Median- Komplexitätsklassen. Ph.D. Thesis (Advisor: R. Reischuk), Aus dem Institut für Theoretische Informatik der Medizinischen Universität zu Lübeck, 1996.
    3. R. Venkatesan. Average-Case Intractability. Ph.D. Thesis (Advisor: L. Levin), Boston University, 1991.


    E-mail Addresses of Authors