JCSS, Volume 69

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 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