JCSS, Volume 69
Volume 69, Number 1, August 2004
Special Issue on Computational Complexity 2002
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
Special Issue on STOC 2003
- 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 update Mon May 20 01:12:22 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page