Volume 69, Number 1, August 2004

• 
  Anne Condon: Guest editor's foreword. 1-2
• 
  Alexander A. Razborov: Resolution lower bounds for perfect matching principles. 3-27
• 
  Frederic Green: The correlation between parity and quadratic polynomials mod 3. 28-44
• 
  Uriel Feige, Daniele Micciancio: The inapproximability of lattice and coding problems with preprocessing. 45-67
• 
  Ryan O'Donnell: Hardness amplification within _NP. 68-94

Volume 69, Number 2, September 2004

• 
  John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Scaled dimension and nonuniform complexity. 97-122
• 
  John Case, Sanjay Jain, Frank Stephan, Rolf Wiehagen: Robust learning--rich and poor. 123-165
• 
  Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. 166-195
• 
  Deepak Chawla, Lin Li, Stephen Scott: On approximating weighted sums with exponentially many terms. 196-234
• 
  Boris Alexeev: Minimal DFA for testing divisibility. 235-243
• 
  Howard Barnum, Michael E. Saks: A lower bound on the quantum query complexity of read-once functions. 244-258
• 
  Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack: On relations between counting communication complexity classes. 259-280
• 
  Andrew Lomonosov, Meera Sitharam, Kihong Park: Network QoS games: stability vs optimality tradeoff. 281-302

Volume 69, Number 3, November 2004

• 
  Sanjeev Khanna, Aravind Srinivasan: Special issue: 35th Annual ACM Symposium on Theory of Computing. 305-
• 
  René Beier, Berthold Vöcking: Random knapsack in expected polynomial time. 306-329
• 
  Mikkel Thorup: Integer priority queues with decrease key in constant time and the single source shortest paths problem. 330-353
• 
  Noga Alon, Asaf Shapira: Testing subgraphs in directed graphs. 354-382
• 
  Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke: Optimal oblivious routing in polynomial time. 383-394
• 
  Iordanis Kerenidis, Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. 395-420
• 
  Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio: Learning functions of k relevant variables. 421-434
• 
  T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani: Cell-probe lower bounds for the partial match problem. 435-447
• 
  Leonid Gurvits: Classical complexity and quantum entanglement. 448-484
• 
  Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. 485-497

Volume 69, Number 4, December 2004

• 
  Mitsunori Ogihara, Till Tantau: On the reducibility of sets inside NP to sets with low information content. 499-524
• 
  Dan Gusfield, Jens Stoye: Linear time algorithms for finding and representing all the tandem repeats in a string. 525-546
• 
  Reuven Bar-Yehuda, Zehavit Kehat: Approximating the dense set-cover problem. 547-561
• 
  Eric Bach, Susan N. Coppersmith, Marcel Paz Goldschen, Robert Joynt, John Watrous: One-dimensional quantum walks with absorbing boundaries. 562-592
• 
  Wolfgang Maass, Henry Markram: On the computational power of circuits of spiking neurons. 593-616
• 
  Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An expressive language for linear spatial database queries. 617-655
• 
  Stefan Szeider: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. 656-674
• 
  Ning Chen, Xiaotie Deng, Xiaoming Sun: On complexity of single-minded auction. 675-687
• 
  He Huang, Jinde Cao, Yuzhong Qu: Global robust stability of delayed neural networks with a class of general activation functions. 688-700

last updated on Sat May 18 06:21:37 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page