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.
- John Case, Sanjay Jain, Frank Stephan, Rolf Wiehagen:
Robust learning--rich and poor.
- 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.
- Deepak Chawla, Lin Li, Stephen Scott:
On approximating weighted sums with exponentially many terms.
- Boris Alexeev:
Minimal DFA for testing divisibility.
- Howard Barnum, Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions.
- Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack:
On relations between counting communication complexity classes.
- Andrew Lomonosov, Meera Sitharam, Kihong Park:
Network QoS games: stability vs optimality tradeoff.
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.
- René Beier, Berthold Vöcking:
Random knapsack in expected polynomial time.
- Mikkel Thorup:
Integer priority queues with decrease key in constant time and the single source shortest paths problem.
- Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs.
- Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke:
Optimal oblivious routing in polynomial time.
- Iordanis Kerenidis, Ronald de Wolf:
Exponential lower bound for 2-query locally decodable codes via a quantum argument.
- Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning functions of k relevant variables.
- T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani:
Cell-probe lower bounds for the partial match problem.
- Leonid Gurvits:
Classical complexity and quantum entanglement.
- Jittat Fakcharoenphol, Satish Rao, Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics.
Volume 69, Number 4, December 2004
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
- Mitsunori Ogihara, Till Tantau:
On the reducibility of sets inside NP to sets with low information content.
- Dan Gusfield, Jens Stoye:
Linear time algorithms for finding and representing all the tandem repeats in a string.
- Reuven Bar-Yehuda, Zehavit Kehat:
Approximating the dense set-cover problem.
- Eric Bach, Susan N. Coppersmith, Marcel Paz Goldschen, Robert Joynt, John Watrous:
One-dimensional quantum walks with absorbing boundaries.
- Wolfgang Maass, Henry Markram:
On the computational power of circuits of spiking neurons.
- Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht:
An expressive language for linear spatial database queries.
- Stefan Szeider:
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable.
- Ning Chen, Xiaotie Deng, Xiaoming Sun:
On complexity of single-minded auction.
- He Huang, Jinde Cao, Yuzhong Qu:
Global robust stability of delayed neural networks with a class of general activation functions.