Welcome to the Speedup WikiEdit

This Wiki provides a user-maintained bibliography on the topic of Speedup in Computational Complexity and Proof Theory. It focuses on computational problems that have no best algorithm--a property that integer and matrix multiplication and coNP-complete problems are conjectured to have. It also includes the related question of proof systems with speedup in proof length. Please feel free to add your papers below. See the related blog here.

General BibliographyEdit

Leonard Berman, On the Structure of Complete Sets: Almost Everywhere Complexity and Infinitely Often Speedup, 17th FOCS (1976), 76–80.

Manuel Blum, On the Size of Machines, Inf. and Control 11 (1967), 257–265.

Manuel Blum, A machine-independent theory of the complexity of recursive functions, J. ACM 14 (1967), 322–36.

Manuel Blum, On effective procedures for speeding up algorithms, J. ACM, 18 (2) (1967), pp. 257–265.

Cristian Calude and Marius Zimand, On three theorems in abstract complexity theory: A topological glimpse, Abstracts of the 2nd International Colloquium on Words, Languages and Combinatorics (Kyoto, Japan), 1992, pp. 11–12.

Cristian Calude, Gabriel Istrate, Marius Zimand, Recursive Baire classification and speedable functions, Mathematical Logic Quarterly, 38:1 (1992),169–178.

Viliam Geffert, A speed-up theorem without tape compression, Theor. Comput. Sci. 118 (1993), no. 1, 49–79.

K. Gödel, Uber die lange von beweisen, Ergebnisse eines Mathematischen Kolloquiums 24 (1936), 745–750.

M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd edition, Springer (1993)

Albert R. Meyer, A Supervisor's Reminiscence. Stockmeyer Symposium Slides. May 2005.

Albert R. Meyer and Patrick C. Fischer, Computational speed-up by effective operators, J. Symb. Log. 37 (1972), 55–68.

Hunter Monroe, Are there natural problems with speedup?, Bulletin of the European Association for Theoretical Computer Science 94 (2008), 212–20.

Nicholas Pippenger and Michael J. Fischer, Relations among complexity measures, J. ACM 26 (1979), 361–381.

Claus-Peter Schnorr and G. Stumpf, A characterization of complexity sequences, Zeitschr. für Math. Logik und Grundlagen der Mathematik 21 (1975), 47–56.

Joel I. Seiferas, Machine-independent complexity theory, in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam (1990), 165–186.

Joel I. Seiferas, Albert R. Meyer, Characterization of realizable space complexities, Annals of Pure and Applied Logic, Vol. 73, Issue 2 (1995), 171-190.

Larry J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, 1974, Doctoral Thesis.

Peter van Emde Boas, Ten years of speedup, MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 13–29.

Klaus Wagner and Gerd Wechsung, Computational Complexity. Reidel Publishing Company, 1986. In particular, Chapter 18 (Speed-Up).

Optimality ResultsEdit

Amir Ben-Amram, The existence of optimal programs, Computability and Complexity from a Programming Perspective (Neil D. Jones, ed.), MIT Press, Cambridge, MA, 1997.

Amir Ben-Amram, N. D. Jones, "Computational Complexity via Programming Languages: Constant Factors Do Matter" Acta Informatica, Vol. 37, no. 2, pp. 83-120, 2000.

Amir Ben-Amram, Tighter Constant-Factor Time Hierarchies, Information Processing Letters 87(1), pp. 37-44, July 2003.

A. M. Ben-Amram, N. H. Christensen, and J. Grue Simonsen, Computational Models with No Linear Speedup. The Chicago Journal of Theoretical Computer Science. Volume 2012, article 7. 2012.

Niels H. Christensen, Levin, Blum and the time optimality of programs , Master’s thesis, DIKU, University of Copehagen, 1999.

Yuri Gurevich, Kolmogorov machines and related issues , Bulletin of the European Association for Theoretical Computer Science 35 (1988), 71–82.

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal, On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography, ECCC TR10-193, December 2010.

Edward A. Hirsch. Optimal acceptors and optimal proof systems. In Proc. 7th Conference on Theory and Applications of Models of Computation. Springer-Verlag, Berlin Heidelberg, 2010.

Leonid A. Levin, Universal sequential search problems, Problems of Information Transmission 9 (1973), 265–66.

Zenon Sadowski, On an optimal deterministic algorithm for SAT, CSL (Georg Gottlob, Etienne Grandjean, and Katrin Seyr, eds.), Lecture Notes in Computer Science, vol. 1584, Springer, 1998, pp. 179–187.

Claus-Peter Schnorr, Optimal algorithms for self-reducible problems, ICALP, 1976, pp. 322–37.

Boris A. Trakhtenbrot, A survey of Russian approaches to perebor (brute-force search) algorithms, Annals of the History of Computing 6 (1984), 384–400.

coNP-complete Problems and Proof ComplexityEdit

Olaf Beyersdorff, Johannes Köbler, Jochen Messner: Nondeterministic functions and the existence of optimal proof systems. Theor. Comput. Sci. 410(38-40): 3839-3855 (2009)

Olaf Beyersdorff, Zenon Sadowski Do there exist complete sets for promise classes? Mathematical Logic Quarterly, 57(6), 2011, p.535.

Yijia Chen, Jörg Flum, Moritz Müller: Hard Instances of Algorithms and Proof Systems. CiE 2012: 118-128

Yijia Chen, Jörg Flum: A Parameterized Halting Problem. The Multivariate Algorithmic Revolution and Beyond 2012: 364-397

Yijia Chen, Jörg Flum: On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT. CSL 2010: 200-214

Yijia Chen, Jörg Flum: A Logic for PTIME and a Parameterized Halting Problem. Fields of Logic and Computation 2010: 251-276

Yijia Chen, Jörg Flum: On p-Optimal Proof Systems and Logics for PTIME. ICALP (2) 2010: 321-332

Yijia Chen, Jörg Flum: On optimal proof systems and logics for PTIME. Electronic Colloquium on Computational Complexity (ECCC) 17: 8 (2010)

Yijia Chen, Jörg Flum: On the complexity of Gödel's proof predicate. J. Symb. Log. 75(1): 239-254 (2010)

Johannes Köbler, Jochen Messner, Jacobo Torán: Optimal proof systems imply complete sets for promise classes. Inf. Comput. 184(1): 71-92 (2003).

Jan Kraj ́ıˇcek and Pavel Pudl ́ak, Propositional proof systems, the consistency of first order theories and the complexity of computations, J. Symb. Log. 54 (1989), 1063–79.

Jochen Messner, On optimal algorithms and optimal proof systems, Lecture Notes in Computer Science 1563 (1999), 541–50.

Hunter Monroe. Speedup for natural problems and noncomputability . Theor. Comput. Sci. 412, 4-5 (February 2011), 478-481.

O. V. Verbitskii, Optimal algorithms for coNP-sets and the EXP=NEXP problem, Mathematical Notes 50 (1991), 796–801.

Integer and Matrix MultiplicationEdit

Daniel Bernstein, Multidigit multiplication for mathematicians, Advances in Applied Mathematics (forthcoming).

Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Christopher Umans, Group theoretic algorithms for matrix multiplication, FOCS ’05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (Washington, DC, USA), IEEE Computer Society, 2005, pp. 379–388.

Don Coppersmith and Shmuel Winograd, On the asymptotic complexity of matrix multiplication, SIAM J. Comput. 11 (1982), 472–492.

Johan Håstad, Tensor rank is NP-complete, J. Algorithms 11 (1990), 644–654.

Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, USA, 1984.

A. Stothers. Ph.D. Thesis, U. Edinburgh, 2010.

Virginia Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, UC Berkeley and Stanford University, 2012.

Monotone-Nonmonotone Gap in Circuit ComplexityEdit

The apparent speedups for integer and matrix multiplication seem to depend on the use of clever cancellation tricks to yield better algorithms. This suggests a relationship with the property of related problems that they have a significant gap between their nonmonotone and monotone circuit complexity (that is, with and without NOT gates). In fact, four of the five problems with such a gap rely upon integer or matrix multiplication: Boolean convolution, Boolean matrix multiplication, perfect matching, and Tardos' problem. This section gives some relevant references.

Noga Alon and Ravi Boppana, The monotone circuit complexity of Boolean functions, Combinatorica 7 (1987), 1–22.

Ravi Boppana and Michael Sipser, The complexity of finite functions, Handbook of Theoretical Computer Science: Volume A: Algorithms and Complexity (J.van Leeuwen, ed.), Elsevier, Amsterdam, 1990, pp. 757–804.

William Hesse, Eric Allender, and David A. Mix Barrington, Uniform constant depth threshold circuits for division and iterated multiplication, J. Comput. Syst. Sci. 65 (2002), 695–716.

Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 (1987), 105–113.

Alexander A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Doklady Akademii Nauk SSSR 281 (1985), 798–801, In Russian. English translation in Soviet Mathematics Doklady, 31:354–357, 1985.

Éva Tardos, The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica 8 (1988), 141–142.

Leslie G. Valiant, Why is Boolean complexity theory difficult?, Proceedings of the London Mathematical Society symposium on Boolean function complexity (New York, NY, USA), Cambridge University Press, 1992, pp. 84–94.

Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, USA, 1987.