![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Journal of the ACM, Volume 56, 2009
Volume 56, Number 1, January 2009
- Kousha Etessami, Mihalis Yannakakis:
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. 1:1-1:66 - Moni Naor, Guy N. Rothblum:
The complexity of online memory checking. 2:1-2:46 - Leslie G. Valiant:
Evolvability. 3:1-3:21 - Moshe Babaioff, Ron Lavi
, Elan Pavlov:
Single-value combinatorial auctions and algorithmic implementation in undominated strategies. 4:1-4:32
Volume 56, Number 2, April 2009
- Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning. 5:1-5:37 - Julia Chuzhoy, Sanjeev Khanna
:
Polynomial flow-cut gaps and hardness of directed cut problems. 6:1-6:28 - Lars Arvestad
, Jens Lagergren, Bengt Sennblad:
The gene evolution model and computing its associated probabilities. 7:1-7:44 - Ran Raz
:
Multi-linear formulas for permanent and determinant are of super-polynomial size. 8:1-8:17 - Glencora Borradaile, Philip N. Klein:
An O(n log n) algorithm for maximum st-flow in a directed planar graph. 9:1-9:30 - Markus Püschel, Peter A. Milder
, James C. Hoe:
Permuting streaming data using RAMs. 10:1-10:34
Volume 56, Number 3, May 2009
- Victor Vianu, Jan Van den Bussche:
Introduction to PODS 2006 special section. 11:1 - Martin Grohe
, André Hernich, Nicole Schweikardt:
Lower bounds for processing data with few random accesses to external memory. 12:1-12:58 - Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin:
Two-variable logic on data trees and XML reasoning. 13:1-13:48 - Xi Chen
, Xiaotie Deng
, Shang-Hua Teng:
Settling the complexity of computing two-player Nash equilibria. 14:1-14:57 - Jan Remy, Angelika Steger:
A quasi-polynomial time approximation scheme for minimum weight triangulation. 15:1-15:47 - Rajeev Alur, P. Madhusudan:
Adding nesting structure to words. 16:1-16:43 - George S. Lueker:
Improved bounds on the average length of longest common subsequences. 17:1-17:38 - Daniel Stefankovic
, Santosh S. Vempala, Eric Vigoda:
Adaptive simulated annealing: A near-optimal connection between sampling and counting. 18:1-18:36
Volume 56, Number 4, June 2009
- Rohit Khandekar, Satish Rao, Umesh V. Vazirani:
Graph partitioning using single commodity flows. 19:1-19:15 - Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. 20:1-20:34 - Dimitris Achlioptas, Aaron Clauset
, David Kempe, Cristopher Moore
:
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. 21:1-21:28 - Kevin Leyton-Brown
, Eugene Nudelman, Yoav Shoham:
Empirical hardness models: Methodology and a case study on combinatorial auctions. 22:1-22:52 - Tim Roughgarden, Mukund Sundararajan:
Quantifying inefficiency in cost-sharing mechanisms. 23:1-23:33 - Hagit Attiya
, Rachid Guerraoui
, Danny Hendler, Petr Kuznetsov:
The complexity of obstruction-free implementations. 24:1-24:33
Volume 56, Number 5, August 2009
- Fedor V. Fomin
, Fabrizio Grandoni
, Dieter Kratsch:
A measure & conquer approach for the analysis of exact algorithms. 25:1-25:32 - Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan:
On the expressiveness and complexity of randomization in finite state monitors. 26:1-26:44 - Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik:
On approximating the ideal random access machine by physical machines. 27:1-27:57 - V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
A unified approach to scheduling on unrelated parallel machines. 28:1-28:31
Volume 56, Number 6, September 2009
- Leonid Libkin, Victor Vianu:
Introduction to PODS 2007 special section. 29:1 - Georg Gottlob
, Zoltán Miklós, Thomas Schwentick:
Generalized hypertree decompositions: NP-hardness and tractable variants. 30:1-30:32 - Balder ten Cate, Carsten Lutz
:
The complexity of query containment in expressive fragments of XPath 2.0. 31:1-31:48 - Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler:
Triangulation and embedding using small sets of beacons. 32:1-32:37 - Rahul Jain
, Jaikumar Radhakrishnan, Pranab Sen:
A property of quantum relative entropy with an application to privacy in quantum communication. 33:1-33:32 - Oded Regev:
On lattices, learning with errors, random linear codes, and cryptography. 34:1-34:40
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.