I/O complexity: The red-blue pebble game
H Jia-Wei, HT Kung - Proceedings of the thirteenth annual ACM …, 1981 - dl.acm.org
In this paper, the red-blue pebble game is proposed to model the input-output complexity of
algorithms. Using the pebble game formulation, a number of lower bound results for the I/O …
algorithms. Using the pebble game formulation, a number of lower bound results for the I/O …
A catalog of complexity classes
DS Johnson - Algorithms and complexity, 1990 - Elsevier
Publisher Summary This chapter discusses the concepts needed for defining the complexity
classes. A complexity class is a set of problems of related resource-based complexity. A …
classes. A complexity class is a set of problems of related resource-based complexity. A …
On relating time and space to size and depth
A Borodin - SIAM journal on computing, 1977 - SIAM
Turing machine space complexity is related to circuit depth complexity. The relationship
complements the known connection between Turing machine time and circuit size, thus …
complements the known connection between Turing machine time and circuit size, thus …
Min cut is NP-complete for edge weighted trees
B Monien, IH Sudborough - Theoretical Computer Science, 1988 - Elsevier
We show that the Min Cut Linear Arrangement Problem (Min Cut) is NP-complete for trees
with polynomial size edge weights and derive from this the NP-completeness of Min Cut for …
with polynomial size edge weights and derive from this the NP-completeness of Min Cut for …
[PDF][PDF] Nondeterminism and the size of two way finite automata
WJ Sakoda, M Sipser - Proceedings of the tenth annual ACM symposium …, 1978 - dl.acm.org
An important goal of the theory of computation is the classification of languages according to
computational difficulty. Classes such as P, NP, and LOGSPACE provide a natural …
computational difficulty. Classes such as P, NP, and LOGSPACE provide a natural …
A polynomial algorithm for the min-cut linear arrangement of trees
M Yannakakis - Journal of the ACM (JACM), 1985 - dl.acm.org
A Polynomial Algorithm for the Min-Cut ILinear Arrangement of Trees Page 1 A Polynomial
Algorithm for the Min-Cut ILinear Arrangement of Trees IMIHALIS YANNAKAKIS A T&T Bell …
Algorithm for the Min-Cut ILinear Arrangement of Trees IMIHALIS YANNAKAKIS A T&T Bell …
Input driven languages are recognized in log n space
B von Braunmühl, R Verbeek - North-Holland Mathematics Studies, 1985 - Elsevier
We show that the class of input driven languages is contained in log n space, an
improvement over the previously known bound of log 2 n/log log log n space [Me 8o]. We …
improvement over the previously known bound of log 2 n/log log log n space [Me 8o]. We …
How limited interaction hinders real communication (and what it means for proof and circuit complexity)
SF De Rezende, J Nordström… - 2016 IEEE 57th Annual …, 2016 - ieeexplore.ieee.org
We obtain the first true size-space trade-offs for the cutting planes proof system, where the
upper bounds hold for size and total space for derivations with constantsize coefficients, and …
upper bounds hold for size and total space for derivations with constantsize coefficients, and …
[PDF][PDF] Asymptotically tight bounds on time-space trade-offs in a pebble game
T Lengauer, RE Tarjan - Journal of the ACM (JACM), 1982 - dl.acm.org
Asymptotically Tight Bounds on Time-Space Trade-offs in a Pebble Game Page 1
Asymptotically Tight Bounds on Time-Space Trade-offs in a Pebble Game THOMAS …
Asymptotically Tight Bounds on Time-Space Trade-offs in a Pebble Game THOMAS …
On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity
T Huynh, J Nordstrom - Proceedings of the forty-fourth annual ACM …, 2012 - dl.acm.org
An active line of research in proof complexity over the last decade has been the study of
proof space and trade-offs between size and space. Such questions were originally …
proof space and trade-offs between size and space. Such questions were originally …