Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 2 Issue 1, November 2010

Cell-Probe Proofs
Yitong Yin
Article No.: 1
DOI: 10.1145/1867719.1867720

We study the nondeterministic cell-probe complexity of static data structures. We introduce cell-probe proofs (CPP), a proof system for the cell-probe model, which describes verification instead of computation in the cell-probe model. We...

Tradeoffs and Average-Case Equilibria in Selfish Routing
Martin Hoefer, Alexander Souza
Article No.: 2
DOI: 10.1145/1867719.1867721

We study Nash equilibria in a selfish routing game on m parallel links with transmission speeds. Each player seeks to communicate a message by choosing one of the links, and each player desires to minimize his experienced transmission time...