default search action
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
Scaled dimension and nonuniform complexity. 97-122 - John Case, Sanjay Jain, Frank Stephan
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
A lower bound on the quantum query complexity of read-once functions. 244-258 - Carsten Damm
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
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
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
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
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
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
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
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.
last updated on 2025-11-14 22:27 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: