@article{Razborov/04,
AUTHOR = {Razborov, Alexander A.},
TITLE = {Resolution lower bounds for perfect matching principles},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {1},
PAGES = {3-27},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {proof complexity, resolution, pigeonhole principle},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Green/04,
AUTHOR = {Green, Frederic},
TITLE = {The correlation between parity and quadratic polynomials mod 3},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {1},
PAGES = {28-44},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {computational complexity, circuit complexity, lower bounds},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Feige-Micciancio/04,
AUTHOR = {Feige, Uriel and Micciancio, Daniele},
TITLE = {The inapproximability of lattice and coding problems with preprocessing},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {1},
PAGES = {45-67},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {point lattices, coding theory, closest vector problem, nearest codeword problem, preprocessing computational complexity, $NP$-hardness, approximation problems},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{ODonnell/04,
AUTHOR = {O'Donnell, Ryan},
TITLE = {Hardness amplification within $NP$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {1},
PAGES = {68-94},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {hardness amplification, $NP$, monotone, XOR lemma, expected bias, noise sensitivity},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Hitchcock-Lutz-Mayordomo/04,
AUTHOR = {Hitchcock, John M. and Lutz, Jack H. and Mayordomo, Elvira},
TITLE = {Scaled dimension and nonuniform complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {97-122},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {resource-bounded dimension, scaled dimension, hausdorff dimension, gales, circuit complexity, kolmogorov complexity, computational complexity},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.09.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Case-Jain-Stephan-Wiehagen/04,
AUTHOR = {Case, John and Jain, Sanjay and Stephan, Frank and Wiehagen, Rolf},
TITLE = {Robust learning --- Rich and poor},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {123-165},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.10.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Demaine-Hajiaghayi-Nishimura-Ragde-Thilikos/04,
AUTHOR = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Nishimura, Naomi and Ragde, Prabhakar and Thilikos, Dimitrios M.},
TITLE = {Approximation algorithms for classes of graphs excluding single-crossing graphs as minors},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {166-195},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.12.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Chawla-Li-Scott/04,
AUTHOR = {Chawla, Deepak and Li, Lin and Scott, Stephen},
TITLE = {On approximating weighted sums with exponentially many terms},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {196-234},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {markov chain monte carlo approximation, winnow, weighted majority, multiplicative weight updates, perceptron, dnf learning, boosting},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Alexeev/04,
AUTHOR = {Alexeev, Boris},
TITLE = {Minimal DFA for testing divisibility},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {235-243},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.02.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Barnum-Saks/04,
AUTHOR = {Barnum, Howard and Saks, Michael},
TITLE = {A lower bound on the quantum query complexity of read-once functions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {244-258},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {quantum query complexity, quantum computation, query complexity, decision tree complexity, read-once functions, lower bounds},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.02.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Damm-Krause-Meinel-Waack/04,
AUTHOR = {Damm, Carsten and Krause, Matthias and Meinel, Christoph and Waack, Stephan},
TITLE = {On relations between counting communication complexity classes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {259-280},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {communication complexity class, protocol, non-determinism, probabilism, modularity, upper bound, lower bound},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Lomonosov-Sitharam-Park/04,
AUTHOR = {Lomonosov, Andrew and Sitharam, Meera and Park, Kihong},
TITLE = {Network QoS games: Stability vs optimality tradeoff},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {2},
PAGES = {281-302},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Beier-Vocking/04,
AUTHOR = {Beier, Rene and V{\"o}cking, Berthold},
TITLE = {Random knapsack in expected polynomial time$^{*1}$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {306-329},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {knapsack problem, exact algorithms, average case analysis},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Thorup/04a,
AUTHOR = {Thorup, Mikkel},
TITLE = {Integer priority queues with decrease key in constant time and the single source shortest paths problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {330-353},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Alon-Shapira/04,
AUTHOR = {Alon, Noga and Shapira, Asaf},
TITLE = {Testing subgraphs in directed graphs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {354-382},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {directed graphs, property testing, core, regularity},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.008},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Azar-Cohen-Fiat-Kaplan-Racke/04,
AUTHOR = {Azar, Yossi and Cohen, Edith and Fiat, Amos and Kaplan, Haim and R{\"a}cke, Harald},
TITLE = {Optimal oblivious routing in polynomial time},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {383-394},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {oblivious routing, oblivious ratio, communication networks},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.010},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Kerenidis-de_Wolf/04a,
AUTHOR = {Kerenidis, Iordanis and de Wolf, Ronald},
TITLE = {Exponential lower bound for 2-query locally decodable codes via a quantum argument},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {395-420},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {quantum computing, locally decodable codes, private information retrieval},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.007},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Mossel-ODonnell-Servedio/04,
AUTHOR = {Mossel, Elchanan and O'Donnell, Ryan and Servedio, Rocco A.},
TITLE = {Learning functions of $k$ relevant variables},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {421-434},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {computational learning theory, pac learning, boolean functions},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Jayram-Khot-Kumar-Rabani/04,
AUTHOR = {Jayram, T.S. and Khot, Subhash and Kumar, Ravi and Rabani, Yuval},
TITLE = {Cell-probe lower bounds for the partial match problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {435-447},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {cell-probe model, partial match problem, nearest neighbor problem, asymmetric communication complexity},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Gurvits/04,
AUTHOR = {Gurvits, Leonid},
TITLE = {Classical complexity and quantum entanglement},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {3},
PAGES = {448-484},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {entanglement, complexity, determinant},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.06.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Fakcharoenphol-Rao-Talwar/04,
AUTHOR = {Fakcharoenphol, Jittat and Rao, Satish and Talwar, Kunal},
TITLE = {A tight bound on approximating arbitrary metrics by tree metrics},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {485-497},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {metrics, embeddings, tree metrics},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.011},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Ogihara-Tantau/04,
AUTHOR = {Ogihara, Mitsunori and Tantau, Till},
TITLE = {On the reducibility of sets inside $NP$ to sets with low information content},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {499-524},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {computational complexity, selectivity, membership comparability, self-reduction, sets with low information content, prover-verifier protocols},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Gusfield-Stoye/04,
AUTHOR = {Gusfield, Dan and Stoye, Jens},
TITLE = {Linear time algorithms for finding and representing all the tandem repeats in a string},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {525-546},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Bar-Yehuda-Kehat/04,
AUTHOR = {Bar-Yehuda, Reuven and Kehat, Zehavit},
TITLE = {Approximating the dense set-cover problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {547-561},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {approximation algorithm, set-cover, vertex-cover},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Bach-Coppersmith-Goldschen-Joynt-Watrous/04,
AUTHOR = {Bach, Eric and Coppersmith, Susan and Goldschen, Marcel Paz and Joynt, Robert and Watrous, John},
TITLE = {One-dimensional quantum walks with absorbing boundaries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {562-592},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {quantum walks, quantum random walks, discrete quantum processes, quantum computation},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.03.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Maass-Markram/04,
AUTHOR = {Maass, Wolfgang and Markram, Henry},
TITLE = {On the computational power of circuits of spiking neurons},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {593-616},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Vandeurzen-Gyssens-van_Gucht/04,
AUTHOR = {Vandeurzen, Luc and Gyssens, Marc and van Gucht, Dirk},
TITLE = {An expressive language for linear spatial database queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {617-655},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {database theory, query languages, constraint databases, linear constraint databases, spatial databases, linear spatial databases, expressiveness},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Szeider/04,
AUTHOR = {Szeider, Stefan},
TITLE = {Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {656-674},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {sat problem, minimal unsatisfiability, fixed-parameter complexity, $d^p$-complete problem, tree-width, bipartite matching, expansion},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.009},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Chen-Deng-Sun/04,
AUTHOR = {Chen, Ning and Deng, Xiaotie and Sun, Xiaoming},
TITLE = {On complexity of single-minded auction},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {675-687},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {combinatorial auctions, single-minded auction, time complexity, communication complexity},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.04.012},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Huang-Cao-Qu/04,
AUTHOR = {Huang, He and Cao, Jinde and Qu, Yuzhong},
TITLE = {Global robust stability of delayed neural networks with a class of general activation functions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {69},
NUMBER = {4},
PAGES = {688-700},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {neural networks, time delays, global robust stability, lyapunov functionals},
URL = {http://dx.doi.org/10.1016/j.jcss.2004.05.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-San Diego-Orlando-Tokyo-Singapore},
}
@article{Mateescu-Salomaa-Yu/04,
AUTHOR = {Mateescu, Alexandru and Salomaa, Arto and Yu, Sheng},
TITLE = {Subword histories and Parikh matrices},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {1-21},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {word, string, subword, scattered subword, number of subwords},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.04.001},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Choi-Zhang/04,
AUTHOR = {Choi, Kwok Pui and Zhang, Louxin},
TITLE = {Sensitivity analysis and efficient method for identifying optimal spaced seeds},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {22-40},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {sequence comparison, pattern matching, filtration technique, spaced seeds, sensitivity analysis, heuristic algorithm},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.04.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Le/04,
AUTHOR = {L{\^e}, Ng\d{o}c-Minh},
TITLE = {Abstract Voronoi diagram in 3-space},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {41-79},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.06.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Becchetti-Leonardi-Muthukrishnan/04,
AUTHOR = {Becchetti, Luca and Leonardi, Stefano and Muthukrishnan, S.},
TITLE = {Average stretch without migration},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {80-95},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {scheduling, average stretch, migration},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.06.001},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Downey-Hirschfeldt-LaForte/04,
AUTHOR = {Downey, Rod G. and Hirschfeldt, Denis R. and LaForte, Geoff},
TITLE = {Randomness and reducibility},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {96-114},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {relative randomness, kolmogorov complexity, algorithmic information theory, solovay reducibility, computably enumerable reals},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.004},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Li/04c,
AUTHOR = {Li, Deng-Feng},
TITLE = {Some measures of dissimilarity in intuitionistic fuzzy structures},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {115-122},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.006},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Anceaume-Fernandez-Mostefaoui-Neiger-Raynal/04,
AUTHOR = {Anceaume, E. and Fern{\'a}ndez, A. and Mostefaoui, A. and Neiger, G. and Raynal, M.},
TITLE = {A necessary and sufficient condition for transforming limited accuracy failure detectors},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {123-133},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {asynchronous distributed system, crash failure, failure detector accuracy, reduction protocol, unreliable failure detector},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.08.003},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Merkle-Stephan/04,
AUTHOR = {Merkle, Wolfgang and Stephan, Frank},
TITLE = {Trees and learning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {134-156},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.08.001},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Anderson-Srinivasan/04,
AUTHOR = {Anderson, James H. and Srinivasan, Anand},
TITLE = {Mixed Pfair/ERfair scheduling of asynchronous periodic tasks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {157-204},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {asynchronous periodic tasks, erfair, fairness, multiprocessors, optimality, pfair, real time, scheduling},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.08.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bshouty-Jackson-Tamon/04,
AUTHOR = {Bshouty, Nader H. and Jackson, Jeffrey C. and Tamon, Christino},
TITLE = {More efficient PAC-learning of DNF with membership queries under the uniform distribution},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {1},
PAGES = {205-234},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {probably approximately learning, membership queries, disjunctive normal form, uniform distribution, fourier transform},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.10.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Achlioptas-Beame-Molloy/04,
AUTHOR = {Achlioptas, Dimitris and Beame, Paul and Molloy, Michael},
TITLE = {A sharp threshold in proof complexity yields lower bounds for satisfiability search},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {238-268},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.011},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Chazelle-Liu/04,
AUTHOR = {Chazelle, Bernard and Liu, Ding},
TITLE = {Lower bounds for intersection searching and fractional cascading in higher dimension},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {269-284},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.003},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Grohe/04,
AUTHOR = {Grohe, Martin},
TITLE = {Computing crossing numbers in quadratic time},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {285-302},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.008},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Klivans-Servedio/04,
AUTHOR = {Klivans, Adam R. and Servedio, Rocco A.},
TITLE = {Learning DNF in time $2^{\~O(n^{1/3})}$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {303-318},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {disjunctive normal form, computational learning theory, polynomial threshold function},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.007},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Schaefer-Stefankovic/04,
AUTHOR = {Schaefer, Marcus and {\v{S}}tefankovi{\v{c}}, Daniel},
TITLE = {Decidability of string graphs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {319-334},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Dunagan-Vempala/04,
AUTHOR = {Dunagan, John and Vempala, Santosh},
TITLE = {Optimal outlier removal in high-dimensional spaces},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {335-373},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.013},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{de_Alfaro-Majumdar/04,
AUTHOR = {de Alfaro, Luca and Majumdar, Rupak},
TITLE = {Quantitative solution of omega-regular games},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {374-397},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {automata, games, $\mu$-calculus, probabilistic algorithm, temporal logic},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.009},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Ambainis/04,
AUTHOR = {Ambainis, Andris},
TITLE = {A new protocol and lower bounds for quantum coin flipping},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {398-416},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.010},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Charikar-Panigrahy/04,
AUTHOR = {Charikar, Moses and Panigrahy, Rina},
TITLE = {Clustering to minimize the sum of cluster diameters},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {417-441},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.014},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Goemans-Williamson/04,
AUTHOR = {Goemans, Michel X. and Williamson, David P.},
TITLE = {Approximation algorithms for {\sc Max}3-{\sc Cut} and other problems via complex semidefinite programming},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {2},
PAGES = {442-470},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {approximation algorithms, semidefinite programming, maximum cut},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.012},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Vikas/04,
AUTHOR = {Vikas, Narayan},
TITLE = {Computational complexity of compaction to irreflexive cycles},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {473-496},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/S0022-0000(03)00034-5},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Palacz/04,
AUTHOR = {Palacz, Wojciech},
TITLE = {Algebraic hierarchical graph transformation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {497-520},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/S0022-0000(03)00064-3},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Kuusela-Ocone/04,
AUTHOR = {Kuusela, P. and Ocone, D.},
TITLE = {Learning with side information: PAC learning bounds},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {521-545},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {uniform convergence of empirical means, learning theory, probably approximately correct learning, dependent data},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.07.005},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Grandjean-Olive/04,
AUTHOR = {Grandjean, Etienne and Olive, F. Fr{\'e}d{\'e}ric},
TITLE = {Graph properties checkable in linear time in the number of vertices},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {546-597},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {linear time, nondeterminism, complexity lower bounds, combinatorial problems, finite model theory, existential second-order logic},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.09.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Sun-Chen-Yeh/04,
AUTHOR = {Sun, Hung-Min and Chen, Bing-Chang and Yeh, Her-Tyan},
TITLE = {On the design of time-stamped signatures},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {598-610},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {authentication, time-stamping, digital signatures, linking schemes, relative temporal authentication, absolute temporal authentication},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.10.003},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Drewes-Engelfriet/04,
AUTHOR = {Drewes, Frank and Engelfriet, Joost},
TITLE = {Branching synchronization grammars with nested tables},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {611-656},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.10.001},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Homan/04,
AUTHOR = {Homan, Christopher M.},
TITLE = {Tight lower bounds on the ambiguity of strong, total, associative, one-way functions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {657-674},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {associativity, computational complexity, cryptocomplexity, cryptography, ambiguity, one-way functions},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.10.004},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Duris-Hromkovic-Inoue/04,
AUTHOR = {{\v{D}}uri{\v{s}}, Pavol and Hromkovi{\v{c}}, Juraj and Inoue, Katsushi},
TITLE = {On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {3},
PAGES = {675-699},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {two-dimensional finite automata, las vegas randomization, nondeterminism, complexity},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.007},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bar-Yossef-Jayram-Kumar-Sivakumar/04,
AUTHOR = {Bar-Yossef, Ziv and Jayram, T.S. and Kumar, Ravi and Sivakumar, D.},
TITLE = {An information statistics approach to data stream and communication complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {702-732},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.006},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Feldman-Karger/04,
AUTHOR = {Feldman, Jon and Karger, David R.},
TITLE = {Decoding turbo-like codes via linear programming},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {733-752},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {turbo codes, linear programming, lp decoding},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.005},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Fischer-Kindler-Ron-Safra-Samorodnitsky/04,
AUTHOR = {Fischer, Eldar and Kindler, Guy and Ron, Dana and Safra, Shmuel and Samorodnitsky, Alex},
TITLE = {Testing juntas},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {753-787},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {property testing, boolean functions, discrete fourier analysis, juntas},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.004},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Franceschini-Grossi-Munro-Pagli/04,
AUTHOR = {Franceschini, Gianni and Grossi, Roberto and Munro, J. Ian and Pagli, Linda},
TITLE = {Implicit $B$-trees: A new data structure for the dictionary problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {788-807},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {searching, $B$-trees, implicit data structures, external memory},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.003},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Klivans-ODonnell-Servedio/04,
AUTHOR = {Klivans, Adam R. and O'Donnell, Ryan and Servedio, Rocco A.},
TITLE = {Learning intersections and thresholds of halfspaces},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {808-840},
YEAR = {2004},
EDITOR = {Blum, E.K.},
KEYWORDS = {computational learning theory, halfspaces, fourier analysis, noise sensitivity, polynomial threshold functions},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Vempala-Wang/04,
AUTHOR = {Vempala, Santosh and Wang, Grant},
TITLE = {A spectral algorithm for learning mixture models},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {68},
NUMBER = {4},
PAGES = {841-860},
YEAR = {2004},
EDITOR = {Blum, E.K.},
URL = {http://dx.doi.org/10.1016/j.jcss.2003.11.008},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}