@article{Chudak-Shmoys/03,
AUTHOR = {Chudak, Fabi{\'{a}}n A. and Shmoys, David B.},
TITLE = {Improved approximation algorithms for the uncapacitated facility location problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {1-25},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {facility location, approximation algorithms, randomized rounding},
URL = {http://dx.doi.org/10.1137/S0097539703405754},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cole-Hariharan/03a,
AUTHOR = {Cole, Richard and Hariharan, Ramesh},
TITLE = {Faster suffix tree construction with missing suffix links},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {26-42},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {suffix tree, parameterized strings, two-dimensional suffix trees, dynamic perfect hashing},
URL = {http://dx.doi.org/10.1137/S0097539701424465},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hromkovic-Schnitger/03b,
AUTHOR = {Hromkovi{\v{c}}, Juraj and Schnitger, Georg},
TITLE = {Nondeterministic communication with a limited number of advice bits},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {43-68},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {communication complexity, nondeterminism},
URL = {http://dx.doi.org/10.1137/S0097539702414622},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cheng-Dey/03,
AUTHOR = {Cheng, Siu-Wing and Dey, Tamal K.},
TITLE = {Quality meshing with weighted Delaunay refinement},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {69-93},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {tetrahedral mesh generation, mesh quality, algorithms, computational geometry, delaunay triangulation, weighted delaunay refinement, sliver},
URL = {http://dx.doi.org/10.1137/S0097539703418808},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Even-Lotker-Ron-Smorodinsky/03,
AUTHOR = {Even, Guy and Lotker, Zvi and Ron, Dana and Smorodinsky, Shakhar},
TITLE = {Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {94-136},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {conflict-free coloring, frequency assignment, approximation algorithms, computational geometry},
URL = {http://dx.doi.org/10.1137/S0097539702431840},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Babai-Gal-Kimmel-Lokam/03,
AUTHOR = {Babai, L{\'{a}}szl{\'{o}} and G{\'{a}}l, Anna and Kimmel, Peter G. and Lokam, Satyanarayana V.},
TITLE = {Communication complexity of simultaneous messages},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {137-166},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {communication complexity, circuit complexity, lower bounds, group theory},
URL = {http://dx.doi.org/10.1137/S0097539700375944},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cramer-Shoup/03,
AUTHOR = {Cramer, Ronald and Shoup, Victor},
TITLE = {Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {167-226},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {cryptography, public-key encryption, chosen ciphertext security, decisional diffie-hellman assumption},
URL = {http://dx.doi.org/10.1137/S0097539702403773},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Burgisser-Cucker/03a,
AUTHOR = {B{\"{u}}rgisser, Peter and Cucker, Felipe},
TITLE = {Counting complexity classes for numeric computations I: Semilinear sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {1},
PAGES = {227-260},
YEAR = {2003},
EDITOR = {Tardos, E.},
KEYWORDS = {counting complexity, real complexity classes, euler characteristic, betti numbers},
URL = {http://dx.doi.org/10.1137/S0097539702415950},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hassin-Levin/04a,
AUTHOR = {Hassin, Refael and Levin, Asaf},
TITLE = {An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {261-268},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithm, spanning tree, matroid intersection, bicriteria optimization},
URL = {http://dx.doi.org/10.1137/S0097539703426775},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Har-Peled-Wang/04,
AUTHOR = {Har-Peled, Sariel and Wang, Yusu},
TITLE = {Shape fitting with outliers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {269-285},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {shape fitting, outliers, approximation},
URL = {http://dx.doi.org/10.1137/S0097539703427963},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lotker-Patt-Shamir-Rosen/04,
AUTHOR = {Lotker, Zvi and Patt-Shamir, Boaz and Ros{\'{e}}n, Adi},
TITLE = {New stability results for adversarial queuing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {286-303},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {adversarial queuing theory, network protocols, stability, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539702413306},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Honkala-Laihonen/04b,
AUTHOR = {Honkala, Iiro and Laihonen, Tero},
TITLE = {On identifying codes in the triangular and square grids},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {304-312},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {identifying code, multiprocessor system, triangular lattice, square lattice, density},
URL = {http://dx.doi.org/10.1137/S0097539703433110},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldberg-Jerrum-Kannan-Paterson/04,
AUTHOR = {Goldberg, Leslie Ann and Jerrum, Mark and Kannan, Sampath and Paterson, Mike},
TITLE = {A bound on the capacity of backoff and acknowledgment-based protocols},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {313-331},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {contention-resolution, backoff, multiple-access channel, stability, protocol},
URL = {http://dx.doi.org/10.1137/S0097539700381851},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Roughgarden/04,
AUTHOR = {Roughgarden, Tim},
TITLE = {Stackelberg scheduling strategies},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {332-350},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {selfish routing, stackelberg equilibria, scheduling},
URL = {http://dx.doi.org/10.1137/S0097539701397059},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gottlob-Pichler/04,
AUTHOR = {Gottlob, Georg and Pichler, Reinhard},
TITLE = {Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {351-378},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {model checking, hypergraphs, tractability, database queries, clique-width, acyclicity, hypertree-width},
URL = {http://dx.doi.org/10.1137/S0097539701396807},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Li-Wang-Zhang/04,
AUTHOR = {Chen, William Y.C. and Li, Xueliang and Wang, Chao and Zhang, Xiaoyan},
TITLE = {The minimum all-ones problem for trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {379-392},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {lamp lighting problem, all-ones problem, graph algorithm, time complexity},
URL = {http://dx.doi.org/10.1137/S0097539703421620},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mohring-Skutella-Stork/04,
AUTHOR = {M{\"{o}}hring, Rolf H. and Skutella, Martin and Stork, Frederik},
TITLE = {Scheduling with AND/OR precedence constraints},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {393-415},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {project scheduling, andor precedence constraints, earliest start schedule, mean payoff games},
URL = {http://dx.doi.org/10.1137/S009753970037727X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldberg-Kelk-Paterson/04,
AUTHOR = {Goldberg, Leslie Ann and Kelk, Steven and Paterson, Mike},
TITLE = {The complexity of choosing an $H$-coloring (nearly) uniformly at random},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {416-432},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {graph coloring, graph homomorphism, computational complexity, random sampling},
URL = {http://dx.doi.org/10.1137/S0097539702408363},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Amano-Maruoka/04a,
AUTHOR = {Amano, Kazuyuki and Maruoka, Akira},
TITLE = {The potential of the approximation method},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {433-447},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {circuit complexity, lower bounds, clique function, approximation method, monotone circuit, negation-limited circuit},
URL = {http://dx.doi.org/10.1137/S009753970138445X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Khuller-Kim-Wan/04,
AUTHOR = {Khuller, Samir and Kim, Yoo-Ah and Wan, Yung-Chun (Justin)},
TITLE = {Algorithms for data migration with cloning},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {448-461},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, multicast, broadcast, gossip},
URL = {http://dx.doi.org/10.1137/S009753970342585X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Icking-Klein-Langetepe-Schuierer-Semrau/04,
AUTHOR = {Icking, Christian and Klein, Rolf and Langetepe, Elmar and Schuierer, Sven and Semrau, Ines},
TITLE = {An optimal competitive strategy for walking in streets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {462-486},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {computational geometry, autonomous robot, competitive strategy, lr-visibility, on-line navigation, path planning, polygon, street},
URL = {http://dx.doi.org/10.1137/S0097539702419352},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alon-Beigel-Kasif-Rudich-Sudakov/04,
AUTHOR = {Alon, Noga and Beigel, Richard and Kasif, Simon and Rudich, Steven and Sudakov, Benny},
TITLE = {Learning a hidden matching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {487-501},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {matchings in graphs, combinatorial search problems, genome sequencing, finite projective planes},
URL = {http://dx.doi.org/10.1137/S0097539702420139},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pan-Wang/04,
AUTHOR = {Pan, Victor Y. and Wang, Xinmao},
TITLE = {On rational number reconstruction and approximation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {2},
PAGES = {502-503},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {rational number reconstruction, rational number approximation, extended euclidean algorithm, lks algorithm, product tree technique},
URL = {http://dx.doi.org/10.1137/S0097539703437181},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Siegel/04,
AUTHOR = {Siegel, Alan},
TITLE = {On universal classes of extremely random constant-time hash functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {505-543},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {hash functions, universal hash functions, hashing, limited independence, optimal speedup, pram emulation, storage-time tradeoff},
URL = {http://dx.doi.org/10.1137/S0097539701386216},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arya-Garg-Khandekar-Meyerson-Munagala-Pandit/04,
AUTHOR = {Arya, Vijay and Garg, Naveen and Khandekar, Rohit and Meyerson, Adam and Munagala, Kamesh and Pandit, Vinayaka},
TITLE = {Local search heuristics for $k$-median and facility location problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {544-562},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {local search, approximation algorithm, facility location},
URL = {http://dx.doi.org/10.1137/S0097539702416402},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kesselman-Lotker-Mansour-Patt-Shamir-Schieber-Sviridenko/04,
AUTHOR = {Kesselman, Alexander and Lotker, Zvi and Mansour, Yishay and Patt-Shamir, Boaz and Schieber, Baruch and Sviridenko, Maxim},
TITLE = {Buffer overflow management in QoS switches},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {563-583},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {buffer overflows, competitive analysis, quality of service, fifo scheduling, deadline scheduling},
URL = {http://dx.doi.org/10.1137/S0097539701399666},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Shen/04,
AUTHOR = {Chen, Xiao and Shen, Jian},
TITLE = {On the Frame-Stewart conjecture about the towers of Hanoi},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {584-589},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {towers of hanoi problem, frame-stewart conjecture, optimal algorithm, frame-stewart algorithm},
URL = {http://dx.doi.org/10.1137/S0097539703431019},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Peer-Pupko-Shamir-Sharan/04,
AUTHOR = {Pe'er, Itsik and Pupko, Tal and Shamir, Ron and Sharan, Roded},
TITLE = {Incomplete directed perfect phylogeny},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {590-607},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {perfect phylogeny, incomplete data, graph sandwich, evolution},
URL = {http://dx.doi.org/10.1137/S0097539702406510},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Elkin-Peleg/04,
AUTHOR = {Elkin, Michael and Peleg, David},
TITLE = {$(1 + \epsilon,\beta)$-spanner constructions for general graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {608-631},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {spanners, graph algorithms, graph partitions},
URL = {http://dx.doi.org/10.1137/S0097539701393384},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buchsbaum-Karloff-Kenyon-Reingold-Thorup/04,
AUTHOR = {Buchsbaum, Adam L. and Karloff, Howard and Kenyon, Claire and Reingold, Nick and Thorup, Mikkel},
TITLE = {OPT versus LOAD in dynamic storage allocation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {632-646},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, dynamic storage allocation, polynomial-time approximation schemes},
URL = {http://dx.doi.org/10.1137/S0097539703423941},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Devroye-Neininger/04,
AUTHOR = {Devroye, Luc and Neininger, Ralph},
TITLE = {Distances and finger search in random binary search trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {647-658},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {random binary search tree, finger search, path distance, limit law, analysis of algorithms},
URL = {http://dx.doi.org/10.1137/S0097539703424521},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Andrews-Zhang/04b,
AUTHOR = {Andrews, Matthew and Zhang, Lisa},
TITLE = {The effects of temporary sessions on network performance},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {659-673},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {packet networks, scheduling, stability, delay bounds, permanent sessions, temporary sessions},
URL = {http://dx.doi.org/10.1137/S0097539702417225},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Halpern-van_der_Meyden-Vardi/04,
AUTHOR = {Halpern, Joseph Y. and van der Meyden, Ron and Vardi, Moshe Y.},
TITLE = {Complete axiomatizations for reasoning about knowledge and time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {674-703},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {complete axiomatizations, knowledge, common knowledge, temporal logic, epistemic logic},
URL = {http://dx.doi.org/10.1137/S0097539797320906},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kortsarz-Krauthgamer-Lee/04,
AUTHOR = {Kortsarz, Guy and Krauthgamer, Robert and Lee, James R.},
TITLE = {Hardness of approximation for vertex-connectivity network design problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {704-720},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, hardness of approximation, vertex connectivity, survivable network design, connectivity augmentation},
URL = {http://dx.doi.org/10.1137/S0097539702416736},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Molloy/04,
AUTHOR = {Molloy, Michael},
TITLE = {The Glauber dynamics on colorings of a graph with high girth and maximum degree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {721-737},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {rapidly mixing markov chains, glauber dynamics, colorings},
URL = {http://dx.doi.org/10.1137/S0097539702401786},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Regev/04a,
AUTHOR = {Regev, Oded},
TITLE = {Quantum computation and lattice problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {3},
PAGES = {738-760},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {lattices, quantum computation, shortest vector problem, hidden subgroup problem},
URL = {http://dx.doi.org/10.1137/S0097539703440678},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vikas/04b,
AUTHOR = {Vikas, Narayan},
TITLE = {Compaction, retraction, and constraint satisfaction},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {761-782},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {computational complexity, graph, coloring, homomorphism, retraction, compaction, constraint satisfaction},
URL = {http://dx.doi.org/10.1137/S0097539701397801},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Barak-Lindell/04,
AUTHOR = {Barak, Boaz and Lindell, Yehuda},
TITLE = {Strict polynomial-time in simulation and extraction},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {783-818},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {zero-knowledge proof systems, proofs of knowledge, expected vs. strict polynomial-time, black-box vs. nonblack-box algorithms},
URL = {http://dx.doi.org/10.1137/S0097539703427975},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{de_Loera-Onn/04,
AUTHOR = {de Loera, Jesus and Onn, Shmuel},
TITLE = {The complexity of three-way statistical tables},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {819-836},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {contingency table, statistical table, data security, statistical disclosure control, Fr{\'{e}}chet bound, confidentiality, marginal statistics, data quality, computational complexity, transportation polytope, transportation problems},
URL = {http://dx.doi.org/10.1137/S0097539702403803},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chekuri-Khanna/04a,
AUTHOR = {Chekuri, Chandra and Khanna, Sanjeev},
TITLE = {On multidimensional packing problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {837-851},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {multidimensional packing, vector scheduling, vector bin packing, packing integer programs, multiprocessor scheduling, bin packing, knapsack, approximation algorithms, hardness of approximation, combinatorial optimization},
URL = {http://dx.doi.org/10.1137/S0097539799356265},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vinodchandran/04b,
AUTHOR = {Vinodchandran, N.V.},
TITLE = {Counting complexity of solvable black-box group problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {852-869},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {computational complexity theory, complexity classes, computational group theory},
URL = {http://dx.doi.org/10.1137/S0097539703420651},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kowalski-Pelc/04b,
AUTHOR = {Kowalski, Dariusz R. and Pelc, Andrzej},
TITLE = {Time of deterministic broadcasting in radio networks with local knowledge},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {870-891},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {broadcasting, distributed, deterministic, radio network},
URL = {http://dx.doi.org/10.1137/S0097539702419339},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Flum-Grohe/04a,
AUTHOR = {Flum, J{\"{o}}rg and Grohe, Martin},
TITLE = {The parameterized complexity of counting problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {892-922},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {counting complexity, parameterized complexity, paths and cycles, descriptive complexity},
URL = {http://dx.doi.org/10.1137/S0097539703427203},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Devroye-Morin-Viola/04,
AUTHOR = {Devroye, Luc and Morin, Pat and Viola, Alfredo},
TITLE = {On worst-case Robin Hood hashing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {923-936},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {open addressing, hashing, robin hood, worst-case search time, collision resolution, probabilistic analysis of algorithms},
URL = {http://dx.doi.org/10.1137/S0097539702403372},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bose-Morin/04a,
AUTHOR = {Bose, Prosenjit and Morin, Pat},
TITLE = {Online routing in triangulations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {937-951},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {routing, online algorithms, delaunay triangulations, shortest path, spanning path},
URL = {http://dx.doi.org/10.1137/S0097539700369387},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schachinger/04,
AUTHOR = {Schachinger, Werner},
TITLE = {Distributional results for costs of partial match queries in asymmetric $k$-dimensional tries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {952-983},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {$k-d$ trie, multidimensional data, partial match retrieval, martingale, asymptotic normality},
URL = {http://dx.doi.org/10.1137/S0097539703425873},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Watanabe/04b,
AUTHOR = {Cai, Jin-Yi and Watanabe, Osamu},
TITLE = {On proving circuit lower bounds against the polynomial-time hierarchy},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {4},
PAGES = {984-1009},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {stringent relativization, circuit complexity, computational complexity, switching lemma, nisan-wigderson generator},
URL = {http://dx.doi.org/10.1137/S0097539703422716},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bar-Noy-Ladner/04,
AUTHOR = {Bar-Noy, Amotz and Ladner, Richard E.},
TITLE = {Efficient algorithms for optimal stream merging for media-on-demand},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1011-1034},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {media-on-demand, stream merging, dynamic programming, monotonicity property},
URL = {http://dx.doi.org/10.1137/S0097539701389245},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dosa-He/04,
AUTHOR = {D{\'{o}}sa, Gy{\"{o}}rgy and He, Yong},
TITLE = {Better online algorithms for scheduling with machine cost},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1035-1051},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {parallel machine scheduling, machine cost, online algorithm, competitive analysis},
URL = {http://dx.doi.org/10.1137/S009753970343395X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Biskup-Paredaens-Schwentick-van_den_Bussche/04,
AUTHOR = {Biskup, Joachim and Paredaens, Jan and Schwentick, Thomas and van den Bussche, Jan},
TITLE = {Solving equations in the relational algebra},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1052-1066},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {relational algebra, equation, nested relation, fagin's theorem, sparse expression, parity},
URL = {http://dx.doi.org/10.1137/S0097539701390859},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Servedio-Gortler/04,
AUTHOR = {Servedio, Rocco A. and Gortler, Steven J.},
TITLE = {Equivalences and separations between quantum and classical learnability},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1067-1092},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {computational learning theory, quantum computation, pac learning, query complexity},
URL = {http://dx.doi.org/10.1137/S0097539704412910},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Toran/04a,
AUTHOR = {Tor{\'{a}}n, Jacobo},
TITLE = {On the hardness of graph isomorphism},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1093-1108},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {graph isomorphism, complexity, reducibility},
URL = {http://dx.doi.org/10.1137/S009753970241096X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{van_Tonder/04,
AUTHOR = {van Tonder, Andr{\'{e}}},
TITLE = {A lambda calculus for quantum computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1109-1135},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum computation, lambda calculus, linear logic, models of computation},
URL = {http://dx.doi.org/10.1137/S0097539703432165},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Xu-Yu/04,
AUTHOR = {Chen, Guantao and Xu, Jun and Yu, Xingxing},
TITLE = {Circumference of graphs with bounded degree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1136-1170},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {bounded degree, 3-connected components, long cycles and paths, circumference},
URL = {http://dx.doi.org/10.1137/S0097539703436473},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Segerlind-Buss-Impagliazzo/04,
AUTHOR = {Segerlind, Nathan and Buss, Sam and Impagliazzo, Russell},
TITLE = {A switching lemma for small restrictions and lower bounds for $k$-DNF resolution},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1171-1200},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {propositional proof complexity, boolean circuit complexity, switching lemmas, lower bounds, $k$-dnfs, resolution, res($k$), circuit bottom fan-in, random restriction, sipser functions, weak pigeonhole principles, random cnfs},
URL = {http://dx.doi.org/10.1137/S0097539703428555},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Orlin-Punnen-Schulz/04,
AUTHOR = {Orlin, James B. and Punnen, Abraham P. and Schulz, Andreas S.},
TITLE = {Approximate local search in combinatorial optimization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1201-1214},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {local search, neighborhood search, approximation algorithms, computational complexity, combinatorial optimization, 0/1-integer programming},
URL = {http://dx.doi.org/10.1137/S0097539703431007},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Havlicek/04,
AUTHOR = {Havlicek, John},
TITLE = {A note on the homotopy type of wait-free atomic snapshot protocol complexes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1215-1222},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {distributed computing, wait-free protocol, atomic snapshot, topology, homotopy, simplicial complex},
URL = {http://dx.doi.org/10.1137/S0097539798337224},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Purdom-van_Gucht-Groth/04,
AUTHOR = {Purdom, Paul W. and van Gucht, Dirk and Groth, Dennis P.},
TITLE = {Average-case performance of the Apriori algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {5},
PAGES = {1223-1260},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {data mining, algorithm analysis, apriori algorithm},
URL = {http://dx.doi.org/10.1137/S0097539703422881},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bartal-Byers-Raz/04,
AUTHOR = {Bartal, Yair and Byers, John W. and Raz, Danny},
TITLE = {Fast, distributed approximation algorithms for positive linear programming with applications to flow control},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1261-1279},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {linear programming, approximation algorithm, primal-dual, flow control},
URL = {http://dx.doi.org/10.1137/S0097539700379383},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schwiegelshohn/04,
AUTHOR = {Schwiegelshohn, Uwe},
TITLE = {Preemptive weighted completion time scheduling of parallel jobs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1280-1308},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {scheduling, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S009753979731501X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hemaspaandra-Hempel-Nickelsen/04,
AUTHOR = {Hemaspaandra, Lane A. and Hempel, Harald and Nickelsen, Arfst},
TITLE = {Algebraic properties for selector functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1309-1337},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {computational complexity theory, $P$-selectivity, $NP$-selectivity, nondeterministic selectivity, selector functions, advice complexity, nonuniform complexity, semifeasible computation, algebraic properties, associativity, commutativity, immunity, printability, tournaments, digraphs},
URL = {http://dx.doi.org/10.1137/S0097539703427550},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feige-Langberg-Schechtman/04,
AUTHOR = {Feige, Uriel and Langberg, Michael and Schechtman, Gideon},
TITLE = {Graphs with tiny vector chromatic numbers and huge chromatic numbers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1338-1368},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {semidefinite programming, chromatic number, independent set, approximation algorithms, property testing},
URL = {http://dx.doi.org/10.1137/S0097539703431391},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Glasser-Selman-Sengupta-Zhang/04,
AUTHOR = {Glasser, Christian and Selman, Alan L. and Sengupta, Samik and Zhang, Liyu},
TITLE = {Disjoint $NP$-pairs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1369-1416},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {disjoint $NP$-pairs, promise problems, propositional proof systems, oracles, symmetry},
URL = {http://dx.doi.org/10.1137/S0097539703425848},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Charikar-Chekuri-Feder-Motwani/04,
AUTHOR = {Charikar, Moses and Chekuri, Chandra and Feder, Tomas and Motwani, Rajeev},
TITLE = {Incremental clustering and dynamic information retrieval},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1417-1440},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {incremental clustering, dynamic information retrieval, minimum diameter clustering, agglomerative clustering, $k$-center, performance guarantee},
URL = {http://dx.doi.org/10.1137/S0097539702418498},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kaufman-Krivelevich-Ron/04,
AUTHOR = {Kaufman, Tali and Krivelevich, Michael and Ron, Dana},
TITLE = {Tight bounds for testing bipartiteness in general graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1441-1483},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {property testing, bipartiteness, randomized algorithms},
URL = {http://dx.doi.org/10.1137/S0097539703436424},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Piotrow/04,
AUTHOR = {Piotr{\'{o}}w, Marek},
TITLE = {Depth optimal sorting networks resistant to $k$ passive faults},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1484-1512},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {fault-tolerant sorting, sorting networks, comparators},
URL = {http://dx.doi.org/10.1137/S0097539799354308},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{McKenzie-Vollmer-Wagner/04,
AUTHOR = {McKenzie, Pierre and Vollmer, Heribert and Wagner, Klaus W.},
TITLE = {Arithmetic circuits and polynomial replacement systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {33},
NUMBER = {6},
PAGES = {1513-1531},
YEAR = {2004},
EDITOR = {Tardos, E.},
KEYWORDS = {arithmetic circuit, counting classes, computational complexity},
URL = {http://dx.doi.org/10.1137/S009753970139207X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}