enter search term and/or author name
Query evaluation via tree-decompositions
Jörg Flum, Markus Frick, Martin Grohe
A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the...
Cosmological lower bound on the circuit complexity of a small problem in logic
Larry Stockmeyer, Albert R. Meyer
An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In...
Correctness properties in a shared-memory parallel language
We study a property of correctness of programs written in a shared-memory parallel language. This property is a semantic equivalence between the parallel program and its sequential version, that we define. We consider some standard...
Towards a theory of cache-efficient algorithms
Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir
We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model,...