@article{Feige-Lapidot-Shamir/99,
AUTHOR = {Feige, Uriel and Lapidot, Dror and Shamir, Adi},
TITLE = {Multiple noninteractive zero knowledge proofs under general assumptions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {1-28},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {hamiltonian cycle, witness indistinguishability},
URL = {http://dx.doi.org/10.1137/S0097539792230010},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ghosh-Leighton-Maggs-Muthukrishnan-Plaxton-Rajaraman-Richa-Tarjan-Zuckerman/99,
AUTHOR = {Ghosh, Bhaskar and Leighton, F.T. and Maggs, Bruce M. and Muthukrishnan, S. and Plaxton, C. Greg and Rajaraman, R. and Richa, Andr{\'e}a W. and Tarjan, Robert E. and Zuckerman, David},
TITLE = {Tight analyses of two local load balancing algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {29-64},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {load balancing, distributed network algorithms},
URL = {http://dx.doi.org/10.1137/S0097539795292208},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{He-Chen/99,
AUTHOR = {He, Xin and Chen, Zhi-Zhong},
TITLE = {An algorithm for shortest paths in bipartite digraphs with concave weight matrices and its applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {65-80},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph algorithm, shortest path, traveling salesman problem, minimum latency tour problem, concave matrix},
URL = {http://dx.doi.org/10.1137/S0097539797322255},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bertsch-Nederhof/99,
AUTHOR = {Bertsch, Eberhard and Nederhof, Mark-Jan},
TITLE = {Regular closure of deterministic languages},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {81-102},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {context-free languages, regular languages},
URL = {http://dx.doi.org/10.1137/S009753979528682X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bonet-Phillips-Warnow-Yooseph/99,
AUTHOR = {Bonet, Maria and Phillips, Cynthia and Warnow, Tandy and Yooseph, Shibu},
TITLE = {Constructing evolutionary trees in the presence of polymorphic characters},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {103-131},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithms, graphs, evolutionary trees},
URL = {http://dx.doi.org/10.1137/S0097539796324636},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Emerson-Jutla/99,
AUTHOR = {Emerson, E. Allen and Jutla, Charanjit S.},
TITLE = {The complexity of tree automata and logics of programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {132-158},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {complexity, tree automata, logics of programs, games},
URL = {http://dx.doi.org/10.1137/S0097539793304741},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Garg-Saran-Vazirani/99,
AUTHOR = {Garg, Naveen and Saran, Huzur and Vazirani, Vijay V.},
TITLE = {Finding separator cuts in planar graphs within twice the optimal},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {159-179},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {separators, planar graphs, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539794271692},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Azar-Broder-Karlin-Upfal/99,
AUTHOR = {Azar, Yossi and Broder, Andrei Z. and Karlin, Anna R. and Upfal, Eli},
TITLE = {Balanced allocations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {180-200},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {urn models, occupancy problems, on-line algorithms, resource allocation, hashing, load balancing},
URL = {http://dx.doi.org/10.1137/S0097539795288490},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bertram-Kretzberg-Lefmann/99,
AUTHOR = {Bertram-Kretzberg, Claudia and Lefmann, Hanno},
TITLE = {The algorithmic aspects of uncrowded hypergraphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {201-230},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {independence number, approximation algorithm},
URL = {http://dx.doi.org/10.1137/S0097539797323716},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Marcinkowski/99,
AUTHOR = {Marcinkowski, Jerzy},
TITLE = {Achilles, Turtle, and undecidable boundedness problems for small DATALOG programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {231-257},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {datalog, query optimization, decidability},
URL = {http://dx.doi.org/10.1137/S0097539797322140},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Leighton-Ma/99,
AUTHOR = {Leighton, Tom and Ma, Yuan},
TITLE = {Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {258-273},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {merging, sorting, circuits, comparator networks, fault-tolerance, lower bounds, probabilistic analysis of algorithms},
URL = {http://dx.doi.org/10.1137/S0097539796305298},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Szkaliczki/99,
AUTHOR = {Szkaliczki, Tibor},
TITLE = {Routing with minimum wire length in the dogleg-free Manhattan model is $NP$-complete},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {274-287},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {single row routing, VLSI, $\cal NP$-complete problems, minimum wire length, interval graph},
URL = {http://dx.doi.org/10.1137/S0097539796303123},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Turau/99,
AUTHOR = {Chen, Weimin and Turau, Volker},
TITLE = {On regular tree embeddings},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {288-301},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {regular trees, directed graph pattern matching, embedding, boolean equations},
URL = {http://dx.doi.org/10.1137/S0097539797324308},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Breutzmann-Lutz/99,
AUTHOR = {Breutzmann, Josef M. and Lutz, Jack H.},
TITLE = {Equivalence of measures of complexity classes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {302-326},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {complexity classes, martingales, resource-bounded measure},
URL = {http://dx.doi.org/10.1137/S0097539796302269},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Anily-Gendreau-Laporte/99,
AUTHOR = {Anily, Shoshana and Gendreau, Michel and Laporte, Gilbert},
TITLE = {The swapping problem on a line},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {327-335},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {the swapping problem, transshipment problem},
URL = {http://dx.doi.org/10.1137/S0097539797323108},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karloff/99,
AUTHOR = {Karloff, Howard},
TITLE = {How good is the Goemans-Williamson MACX CUT algorithm?},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {1},
PAGES = {336-350},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {max cut, semidefinite programming, approximation algorithm, optimization},
URL = {http://dx.doi.org/10.1137/S0097539797321481},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chor-Nelson/99,
AUTHOR = {Chor, Benny and Nelson, Lee-Bath},
TITLE = {Solvability in asynchronous environments II: Finite interactive tasks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {351-377},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {solvability, asynchronous distributed systems, fault tolerance, randomized algorithms, consensus, interactive tasks, decision tasks, adversary scheduler},
URL = {http://dx.doi.org/10.1137/S0097539795294979},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Eschen-Hayward-Spinrad-Sritharan/99,
AUTHOR = {Eschen, Elaine and Hayward, Ryan B. and Spinrad, Jeremy and Sritharan, R.},
TITLE = {Weakly triangulated comparability graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {378-386},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {weakly triangulated, comparability, partial orders, algorithm},
URL = {http://dx.doi.org/10.1137/S0097539797322334},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bubley-Dyer-Greenhill-Jerrum/99,
AUTHOR = {Bubley, Russ and Dyer, Martin and Greenhill, Catherine and Jerrum, Mark},
TITLE = {On approximately counting colorings of small degree graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {387-400},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph colorings, rapidly mixing markov chains, approximate counting, transportation problems},
URL = {http://dx.doi.org/10.1137/S0097539798338175},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bellantoni-Niggl/99,
AUTHOR = {Bellantoni, Stephen J. and Niggl, Karl-Heinz},
TITLE = {Ranking primitive recursions: The low Grzegorczyk classes revisited},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {401-415},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {subrecursion, computational complexity, predicativity, ramified recursion, Heinermann classes, polynomial time, linear space},
URL = {http://dx.doi.org/10.1137/S009753979528175X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goodrich/99,
AUTHOR = {Goodrich, Michael T.},
TITLE = {Communication-efficient parallel sorting},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {416-432},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parallel algorithms, parallel sorting, parallel processing},
URL = {http://dx.doi.org/10.1137/S0097539795294141},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rieger/99,
AUTHOR = {Rieger, J.H.},
TITLE = {Proximity in arrangements of algebraic sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {433-458},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {$k$ nearest points, voronoi regions, bifurcation sets, critical points, symbolic computation},
URL = {http://dx.doi.org/10.1137/S0097539796300945},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {see Erratum in SIAM J. Comp., Vol. 31, 2001-2002, No. 3, 987-987},
}
@article{Albers/99a,
AUTHOR = {Albers, Susanne},
TITLE = {Better bounds for online scheduling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {459-473},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {makespan minimization, online algorithm, competitive analysis},
URL = {http://dx.doi.org/10.1137/S0097539797324874},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bhatt-Greenberg-Leighton-Liu/99,
AUTHOR = {Bhatt, Sandeep and Greenberg, David and Leighton, Tom and Liu, Pangfeng},
TITLE = {Tight bounds for on-line tree embeddings},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {474-491},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph embedding, randomized algorithm},
URL = {http://dx.doi.org/10.1137/S0097539796308710},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karger/99,
AUTHOR = {Karger, David R.},
TITLE = {A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {492-514},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {network reliability, approximation scheme, minimum cut},
URL = {http://dx.doi.org/10.1137/S0097539796298340},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arkin-Chiang-Mitchell-Skiena-Yang/99,
AUTHOR = {Arkin, Esther M. and Chiang, Yi-Jen and Mitchell, Joseph S.B. and Skiena, Steven S. and Yang, Tae-Cheon},
TITLE = {On the maximum scatter Traveling Salesperson Problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {515-544},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {traveling salesperson problem, traveling salesman problem, maximum scatter tsp, bottleneck tsp, Hamiltonian cycle/path, approximation algorithms, matching, optimization, posa conjecture, Dirac's theorem},
URL = {http://dx.doi.org/10.1137/S0097539797320281},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Downey-Fellows-Vardy-Whittle/99,
AUTHOR = {Downey, Rod G. and Fellows, Michael R. and Vardy, Alexander and Whittle, Geoff},
TITLE = {The parametrized complexity of some fundamental problems in coding theory},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {545-570},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parametrized complexity, linear codes, decoding, codes in graphs, integer lattices},
URL = {http://dx.doi.org/10.1137/S0097539797323571},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karkkainen-Ukkonen/99,
AUTHOR = {K{\"a}rkk{\"a}inen, Juha and Ukkonen, Esko},
TITLE = {Two- and higher-dimensional pattern matching in optimal expected time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {571-589},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {multidimensional matching, average case analysis, approximate matching},
URL = {http://dx.doi.org/10.1137/S0097539794275872},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Li-Tromp-Vitanyi/99,
AUTHOR = {Buhrman, Harry and Li, Ming and Tromp, John and Vit{\'a}nyi, Paul},
TITLE = {Kolmogorov random graphs and the incompressibility method},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {590-599},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {kolmogorov complexity, incompressibility method, random graphs, enumeration of graphs, algorithmic information theory},
URL = {http://dx.doi.org/10.1137/S0097539797327805},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bruell-Ghosh-Karaata-Pemmaraju/99,
AUTHOR = {Bruell, Steven C. and Ghosh, Sukumar and Karaata, Mehmet Hakan and Pemmaraju, Sriram V.},
TITLE = {Self-stabilizing algorithms for finding centers and medians of trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {600-614},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {center, distributed algorithm, median, self-stabilization, tree},
URL = {http://dx.doi.org/10.1137/S0097539798427156},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Andrews-Leighton-Metaxas-Zhang/99,
AUTHOR = {Andrews, Matthew and Leighton, Tom and Metaxas, P. Takis and Zhang, Lisa},
TITLE = {Automatic methods for hiding latency in parallel and distributed computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {615-647},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {hiding latency, parallel and distributed computation, linear and two-dimensional arrays, complementary slackness},
URL = {http://dx.doi.org/10.1137/S0097539797326502},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Srinivasan/99,
AUTHOR = {Srinivasan, Aravind},
TITLE = {Improved approximation guarantees for packing and covering integer programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {648-670},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, combinatorial optimization, correlation inequalities, covering integer programs, derandomization, integer programming, linear programming, linear relaxations, packing integer programs, positive correlation, randomized rounding, rounding theorems},
URL = {http://dx.doi.org/10.1137/S0097539796314240},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ruskey-Sawada/99,
AUTHOR = {Ruskey, Frank and Sawada, Joe},
TITLE = {An efficient algorithm for generating necklaces with fixed density},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {671-684},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {necklaces, lyndon words, fixed density, cat algorithm, generate, difference covers},
URL = {http://dx.doi.org/10.1137/S0097539798344112},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Nedev/99,
AUTHOR = {Nedev, Zhivko Prodanov},
TITLE = {Finding an even simple path in a directed planar graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {2},
PAGES = {685-695},
YEAR = {1999},
EDITOR = {Yannakakis, M.},
KEYWORDS = {labeled directed graphs, $NP$-completeness, polynomial-time algorithms, regular expressions, simple paths, planar graphs},
URL = {http://dx.doi.org/10.1137/S0097539797330343},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aggarwal-Coppersmith-Khanna-Motwani-Schieber/00,
AUTHOR = {Aggarwal, Alok and Coppersmith, Don and Khanna, Sanjeev and Motwani, Rajeev and Schieber, Baruch},
TITLE = {The angular-metric Traveling Salesman Problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {697-711},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {angle metric, approximation algorithms, combinatorial optimization, computational complexity, extremal point sets, robotics, traveling salesman problem},
URL = {http://dx.doi.org/10.1137/S0097539796312721},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Natarajan/00,
AUTHOR = {Natarajan, B.},
TITLE = {On learning functions from noise-free and noisy samples via Occam's razor},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {712-727},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {probably approximate learning, noisy data},
URL = {http://dx.doi.org/10.1137/S0097539794277111},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Levene-Loizou/00,
AUTHOR = {Levene, Mark and Loizou, George},
TITLE = {Navigation in hypertext is easy only sometimes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {728-760},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {hypertext, navigation, trail query, temporal logic, finite automata, computational complexity},
URL = {http://dx.doi.org/10.1137/S0097539795282730},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Wu-Lancia-Bafna-Chao-Ravi-Tang/00,
AUTHOR = {Wu, Bang Ye and Lancia, Giuseppe and Bafna, Vineet and Chao, Kun-Mao and Ravi, R. and Tang, Chuan Yi},
TITLE = {A polynomial-time approximation scheme for minimum routing cost spanning trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {761-778},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, network design, spanning trees, computational biology},
URL = {http://dx.doi.org/10.1137/S009753979732253X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boldi-Vigna/00a,
AUTHOR = {Boldi, Paolo and Vigna, Sebastiano},
TITLE = {Complexity of deciding sense of direction},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {779-789},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {distributed systems, computational complexity, sense of direction, cayley graphs},
URL = {http://dx.doi.org/10.1137/S0097539796310801},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fiat-Naor/00,
AUTHOR = {Fiat, Amos and Naor, Moni},
TITLE = {Rigorous time/space trade-offs for inverting functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {790-803},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {cryptography, cryptanalysis, one-way functions, randomized algorithms, random graphs, hashing data encryption standard},
URL = {http://dx.doi.org/10.1137/S0097539795280512},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dolev-Kranakis-Krizanc-Peleg/00,
AUTHOR = {Dolev, Shlomi and Kranakis, Evangelos and Krizanc, Danny and Peleg, David},
TITLE = {Bubbles: Adaptive routing scheme for high-speed dynamic networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {804-833},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {adaptability, dynamic, fiber optics, communication network, routing},
URL = {http://dx.doi.org/10.1137/S0097539797316610},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldberg-Jerrum/00,
AUTHOR = {Goldberg, Leslie Ann and Jerrum, Mark},
TITLE = {Randomly sampling molecules},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {834-853},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {P{\'{o}}lya theory, random graphs, structural isomers},
URL = {http://dx.doi.org/10.1137/S0097539797318864},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Decatur-Goldreich-Ron/00,
AUTHOR = {Decatur, Scott E. and Goldreich, Oded and Ron, Dana},
TITLE = {Computational sample complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {854-879},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational learning theory, information vs. efficient computation, pseudo-random functions, error correcting codes, wire-tap channel},
URL = {http://dx.doi.org/10.1137/S0097539797325648},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kaplan-Shamir-Tarjan/00,
AUTHOR = {Kaplan, Haim and Shamir, Ron and Tarjan, Robert E.},
TITLE = {A faster and simpler algorithm for sorting signed permutations by reversals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {880-892},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {sorting permutations, reversal distance, computational molecular biology},
URL = {http://dx.doi.org/10.1137/S0097539798334207},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kosaraju-Manzini/00,
AUTHOR = {Kosaraju, S. Rao and Manzini, Giovanni},
TITLE = {Compression of low entropy strings with Lempel-Ziv algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {893-911},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {data compression, Lempel-Ziv parsing, empirical entropy},
URL = {http://dx.doi.org/10.1137/S0097539797331105},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Efrat-Sharir/00,
AUTHOR = {Agarwal, Pankaj K. and Efrat, Alon and Sharir, Micha},
TITLE = {Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {912-953},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {arrangements, divide-and-conquer, range searching, nearest-neighbor searching, parametric searching, geometric optimization},
URL = {http://dx.doi.org/10.1137/S0097539795295936},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sweedyk/00,
AUTHOR = {Sweedyk, Z.},
TITLE = {A $2\frac{1}{2}$-approximation algorithm for shortest superstring},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {954-986},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithm, shortest superstring, shotgun sequencing, data compression},
URL = {http://dx.doi.org/10.1137/S0097539796324661},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Macarie/00,
AUTHOR = {Macarie, Ioan I.},
TITLE = {On the structure of logspace probabilistic complexity classes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {987-1007},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {multihead finite automata, heads hierarchy, probabilistic computation, probabilistic turing machines, Arthur-Merlin games, games against nature, logspace reductions},
URL = {http://dx.doi.org/10.1137/S0097539796298339},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Miyazawa-Wakabayashi/00,
AUTHOR = {Miyazawa, F.K. and Wakabayashi, Y.},
TITLE = {Approximation algorithms for the orthogonal $Z$-oriented three-dimensional packing problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {1008-1029},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, three-dimensional packing, asymptotic performance bound},
URL = {http://dx.doi.org/10.1137/S009753979631391X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Willard/00,
AUTHOR = {Willard, Dan E.},
TITLE = {Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {3},
PAGES = {1030-1049},
YEAR = {1999-2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {sorting, searching, hashing, computational geometry, multidimensional retrieval},
URL = {http://dx.doi.org/10.1137/S0097539797322425},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kimbrel-Karlin/00,
AUTHOR = {Kimbrel, Tracy and Karlin, Anna R.},
TITLE = {Near-optimal parallel prefetching and caching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1051-1082},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithms, prefetching, caching, file systems, operating systems},
URL = {http://dx.doi.org/10.1137/S0097539797326976},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pacholski-Szwast-Tendera/00,
AUTHOR = {Pacholski, Leszek and Szwast, Wies{\l}aw and Tendera, Lidia},
TITLE = {Complexity results for first-order two-variable logic with counting},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1083-1117},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {decision problem, computational complexity, first-order logic},
URL = {http://dx.doi.org/10.1137/S0097539797323005},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Reinhardt-Allender/00,
AUTHOR = {Reinhardt, Klaus and Allender, Eric},
TITLE = {Making nondeterminism unambiguous},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1118-1131},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {nondeterministic space, unambiguous computation, nlog, ulog, logcfl},
URL = {http://dx.doi.org/10.1137/S0097539798339041},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldreich-Safra/00,
AUTHOR = {Goldreich, Oded and Safra, Shmuel},
TITLE = {A combinatorial consistency lemma with application to proving the $PCP$ theorem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1132-1154},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parallelization of probabilistic proof systems, probabilistically checkable proofs (pcp), $NP$, low-degree tests},
URL = {http://dx.doi.org/10.1137/S0097539797315744},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rajagopalan-Schulman/00,
AUTHOR = {Rajagopalan, Sridhar and Schulman, Leonard J.},
TITLE = {Verification of identities},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1155-1163},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computer aided verification, randomized algorithms},
URL = {http://dx.doi.org/10.1137/S0097539797325387},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Albers-Henzinger/00,
AUTHOR = {Albers, Susanne and Henzinger, Monika R.},
TITLE = {Exploring unknown environments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1164-1188},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {directed graph, exploration algorithm},
URL = {http://dx.doi.org/10.1137/S009753979732428X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kilian-Kushilevitz-Micali-Ostrovsky/00,
AUTHOR = {Kilian, Joe and Kushilevitz, Eyal and Micali, Silvio and Ostrovsky, Rafail},
TITLE = {Reducibility and completeness in private computations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1189-1208},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {private computation, reducibility, completeness, oblivious-transfer},
URL = {http://dx.doi.org/10.1137/S0097539797321742},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Grolmusz-Tardos/00,
AUTHOR = {Grolmusz, Vince and Tardos, G{\'a}bor},
TITLE = {Lower bounds for $(MOD_p - MOD_m)$ circuits},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1209-1222},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {lower bounds, modular gates, composite modulus},
URL = {http://dx.doi.org/10.1137/S0097539798340850},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Klenk-Tu/00,
AUTHOR = {Chen, Danny Z. and Klenk, Kevin S. and Tu, Hung-Yi T.},
TITLE = {Shortest path queries among weighted obstacles in the rectilinear plane},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1223-1246},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational geometry, path planning, data structures, analysis of algorithms},
URL = {http://dx.doi.org/10.1137/S0097539796307194},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Kao/00,
AUTHOR = {Chen, Zhi-Zhong and Kao, Ming-Yang},
TITLE = {Reducing randomness via irrational numbers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1247-1256},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {polynomial identification, galois theory, randomized algorithms, parallel algorithms, program checking, perfect matchings, multiset equality test},
URL = {http://dx.doi.org/10.1137/S0097539798341600},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lin-Farrahi-Sarrafzadeh/00,
AUTHOR = {Lin, Wei-Liang and Farrahi, Amir H. and Sarrafzadeh, M.},
TITLE = {On the power of logic resynthesis},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1257-1289},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {VLSI design, linear arrangement, graphs and large scale networks, resynthesis, timing, VLSI layout},
URL = {http://dx.doi.org/10.1137/S0097539796335480},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Barve-Grove-Vitter/00,
AUTHOR = {Barve, Rakesh D. and Grove, Edward F. and Vitter, Jeffrey Scott},
TITLE = {Application-controlled paging for a shared cache},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1290-1303},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {caching, application-controlled, competitive, online, randomized},
URL = {http://dx.doi.org/10.1137/S0097539797324278},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boppana-Narayanan/00,
AUTHOR = {Boppana, Ravi B. and Narayanan, Babu O.},
TITLE = {Perfect-information leader election with optimal resilience},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1304-1320},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {distributed computing, fault tolerance, leader election, perfect information, probabilistic methods},
URL = {http://dx.doi.org/10.1137/S0097539796307182},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aggarwal-Kleinberg-Williamson/00,
AUTHOR = {Aggarwal, Alok and Kleinberg, Jon and Williamson, David P.},
TITLE = {Node-disjoint paths on the mesh and a new trade-off in VLSI layout},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1321-1333},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {combinatorial optimization, VLSI layout, disjoint paths problem},
URL = {http://dx.doi.org/10.1137/S0097539796312733},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mitchell-Vavasis/00,
AUTHOR = {Mitchell, Scott A. and Vavasis, Stephen A.},
TITLE = {Quality mesh generation in higher dimensions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1334-1370},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {triangulation, aspect ratio, tetrahedra, mesh generation, polyhedron},
URL = {http://dx.doi.org/10.1137/S0097539796314124},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan-van_der_Meyden/00,
AUTHOR = {Chan, Edward P.F. and van der Meyden, Ron},
TITLE = {Containment and optimization of object-preserving conjunctive queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {4},
PAGES = {1371-1400},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {object-oriented database, query optimization, conjunctive queries, containment, equivalence, minimization, complexity},
URL = {http://dx.doi.org/10.1137/S0097539794262446},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boissonnat-Preparata/00,
AUTHOR = {Boissonnat, Jean-Daniel and Preparata, Franco P.},
TITLE = {Robust plane sweep for intersecting segments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1401-1421},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational geometry, segment intersection, plane sweep, robust algorithms},
URL = {http://dx.doi.org/10.1137/S0097539797329373},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Grove-Murali-Vitter/00,
AUTHOR = {Agarwal, Pankaj K. and Grove, Edward F. and Murali, T.M. and Vitter, Jeffrey Scott},
TITLE = {Binary space partitions for fat rectangles},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1422-1448},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {binary space partitions, rectangles, aspect ratio, computational geometry, computer graphics, solid modelling},
URL = {http://dx.doi.org/10.1137/S0097539797320578},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Saks-Zaharoglou/00,
AUTHOR = {Saks, Michael and Zaharoglou, Fotios},
TITLE = {Wait-free $k$-set agreement is impossible: The topology of public knowledge},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1449-1483},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {distributed computing, consensus, Sperner's lemma, wait-free},
URL = {http://dx.doi.org/10.1137/S0097539796307698},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dagum-Karp-Luby-Ross/00,
AUTHOR = {Dagum, Paul and Karp, Richard and Luby, Michael and Ross, Sheldon},
TITLE = {An optimal algorithm for Monte Carlo estimation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1484-1496},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {stopping rule, approximation algorithm, monte carlo estimation, sequential estimation, stochastic approximation},
URL = {http://dx.doi.org/10.1137/S0097539797315306},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Fortnow-van_Melkebeek-Torenvliet/00,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and van Melkebeek, Dieter and Torenvliet, Leen},
TITLE = {Separating complexity classes using autoreducibility},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1497-1520},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {complexity classes, completeness, autoreducibility, coherence},
URL = {http://dx.doi.org/10.1137/S0097539798334736},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{la_Poutre/00,
AUTHOR = {la Poutr{\'e}, Han},
TITLE = {Maintenance of 2- and 3-edge-connected components of graphs II},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1521-1549},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {analysis of algorithms, dynamic data structures, edge connectivity, vertex connectivity},
URL = {http://dx.doi.org/10.1137/S0097539793257770},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vincent-Levene/00,
AUTHOR = {Vincent, Millist W. and Levene., Mark},
TITLE = {Restructuring partitioned normal form relations without information loss},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1550-1567},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {database, nested relations, multivalued dependency, partitioned normal form},
URL = {http://dx.doi.org/10.1137/S0097539797326319},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kao-Wang/00,
AUTHOR = {Kao, Ming-Yang and Wang, Jie},
TITLE = {Linear-time approximation algorithms for computing numerical summation with provably small errors},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1568-1576},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {floating-point summation, error analysis, addition trees, combinatorial optimization, $NP$-hardness, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539798341594},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sellen-Choi-Yap/00,
AUTHOR = {Sellen, J{\"u}rgen and Choi, Joonsoo and Yap, Chee-Keng},
TITLE = {Precision-sensitive Euclidean shortest path in 3-space},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1577-1595},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {shortest path, exact geometric algorithms, bit complexity, precision-sensitivity},
URL = {http://dx.doi.org/10.1137/S0097539798340205},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Etzioni-Hanks-Jiang-Madani/00,
AUTHOR = {Etzioni, Oren and Hanks, Steve and Jiang, Tao and Madani, Omid},
TITLE = {Optimal information gathering on the Internet with time and cost constraints},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1596-1620},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithm, batched policy, computational complexity, information gathering, information retrieval, internet, scheduling, time and cost trade off, world wide web},
URL = {http://dx.doi.org/10.1137/S0097539797314465},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Stacho-Vrto/00,
AUTHOR = {Stacho, Ladislav and Vr{\v{t}}o, Imrich},
TITLE = {Virtual path layouts in ATM networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1621-1629},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {atm network, congestion, hop-number, virtual paths layout},
URL = {http://dx.doi.org/10.1137/S0097539796308151},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ergun-Kumar-Sivakumar/00,
AUTHOR = {Erg{\"u}n, Funda and Kumar, S. Ravi and Sivakumar, D.},
TITLE = {Self-testing without the generator bottleneck},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1630-1651},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {program correctness, self-testing, generator bottleneck},
URL = {http://dx.doi.org/10.1137/S0097539796311168},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Benedikt-Libkin/00a,
AUTHOR = {Benedikt, Michael and Libkin, Leonid},
TITLE = {Safe constraint queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1652-1682},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {constraints, databases, first-order logic, query safety},
URL = {http://dx.doi.org/10.1137/S0097539798342484},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Khanna-Liberatore/00,
AUTHOR = {Khanna, Sanjeev and Liberatore, Vincenzo},
TITLE = {On broadcast disk paging},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1683-1702},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {design of algorithms, online algorithms, competitive analysis, paging, distributed systems, client-server architecture, broadcast disks},
URL = {http://dx.doi.org/10.1137/S0097539798341399},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Czumaj-Meyer_auf_der_Heide-Stemann/00,
AUTHOR = {Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker},
TITLE = {Contention resolution in hashing based shared memory simulations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1703-1739},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {pram, distributed memory machine, randomized shared memory simulations, hashing},
URL = {http://dx.doi.org/10.1137/S009753979529564X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dor-Halperin-Zwick/00,
AUTHOR = {Dor, Dorit and Halperin, Shay and Zwick, Uri},
TITLE = {All-pairs almost shortest paths},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {5},
PAGES = {1740-1759},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph algorithms, shortest paths, approximation algorithms, spanners, emulators},
URL = {http://dx.doi.org/10.1137/S0097539797327908},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Henzinger/00b,
AUTHOR = {Henzinger, Monika R.},
TITLE = {Improved data structures for fully dynamic biconnectivity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1761-1815},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {dynamic graph algorithms, biconnectivity, data structures},
URL = {http://dx.doi.org/10.1137/S0097539794263907},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lennerstad-Lundberg/00,
AUTHOR = {Lennerstad, H{\aa}kan and Lundberg, Lars},
TITLE = {Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1816-1838},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {dynamic allocation, cluster allocation, static allocation, scheduling, multiprocessor, optimal performance, extremal combinatorics, combinatorial formula, 0,1-matrices, optimal partition},
URL = {http://dx.doi.org/10.1137/S0097539799294398},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{von_zur_Gathen-Shparlinski/00,
AUTHOR = {von zur Gathen, Joachim and Shparlinski, Igor E.},
TITLE = {The CREW PRAM complexity of modular inversion},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1839-1857},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {modular inversion, parallel computation, crew pram complexity, exponential sums},
URL = {http://dx.doi.org/10.1137/S0097539797328070},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kapoor/00,
AUTHOR = {Kapoor, Sanjiv},
TITLE = {Dynamic maintenance of maxima of 2-D point sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1858-1877},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {maximal points, dynamic maintenance, balanced trees},
URL = {http://dx.doi.org/10.1137/S0097539798348365},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Lipton-Zalcstein/00,
AUTHOR = {Cai, Jin-Yi and Lipton, Richard J. and Zalcstein, Yechezkel},
TITLE = {The complexity of the A B C problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1878-1888},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {polynomial-time algorithm, membership problem, semigroup, commutative, lattice},
URL = {http://dx.doi.org/10.1137/S0097539794276853},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Malkhi-Reiter-Wool/00,
AUTHOR = {Malkhi, Dahlia and Reiter, Michael K. and Wool, Avishai},
TITLE = {The load and availability of Byzantine quorum systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1889-1906},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quorum systems, byzantine failures, replication, load, availability, distributed computing},
URL = {http://dx.doi.org/10.1137/S0097539797325235},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Blum-Chalasani/00,
AUTHOR = {Blum, Avrim and Chalasani, Prasad},
TITLE = {An online algorithm for improving performance in navigation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1907-1938},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {online algorithms, robot path planning, exploration vs. exploitation, learning, navigation, unfamiliar terrain, competitive analysis, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539795290593},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bonet-Pitassi-Raz/00,
AUTHOR = {Bonet, Maria Luisa and Pitassi, Toniann and Raz, Ran},
TITLE = {On interpolation and automatization for Frege systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1939-1967},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {propositional proof systems, frege proof systems, threshold circuits, Diffie-Hellman},
URL = {http://dx.doi.org/10.1137/S0097539798353230},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Erickson/00,
AUTHOR = {Erickson, Jeff},
TITLE = {Space-time tradeoffs for emptiness queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1968-1996},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {lower bounds, range searching, space-time tradeoff, partition graph},
URL = {http://dx.doi.org/10.1137/S0097539798337212},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Adler-Byers-Karp/00,
AUTHOR = {Adler, Micah and Byers, John W. and Karp, Richard M.},
TITLE = {Parallel sorting with limited bandwidth},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {1997-2015},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parallel sorting, limited bandwidth, pram, logp, bsp},
URL = {http://dx.doi.org/10.1137/S0097539797315884},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Har-Peled/00,
AUTHOR = {Har-Peled, Sariel},
TITLE = {Constructing planar cuttings in theory and practice},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {2016-2039},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {cuttings, range-searching, computational geometry},
URL = {http://dx.doi.org/10.1137/S0097539799350232},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aguilera-Chen-Toueg/00,
AUTHOR = {Aguilera, Marcos Kawazoe and Chen, Wei and Toueg, Sam},
TITLE = {On quiescent reliable communication},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {2040-2073},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithms, reliability, reliable communication, quiescence, asynchronous systems, heartbeat, crash failures, link failures, failure detection, fault-tolerance, message passing, processor failures},
URL = {http://dx.doi.org/10.1137/S0097539798341296},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Trevisan-Sorkin-Sudan-Williamson/00,
AUTHOR = {Trevisan, Luca and Sorkin, Gregory B. and Sudan, Madhu and Williamson, David P.},
TITLE = {Gadgets, approximation, and linear programming},
JOURNAL = {SIAM J. Comput.},
VOLUME = {29},
NUMBER = {6},
PAGES = {2074-2097},
YEAR = {2000},
EDITOR = {Yannakakis, M.},
KEYWORDS = {combinatorial optimization, approximation algorithms, reductions, intractability, $NP$-completeness, probabilistic proof systems},
URL = {http://dx.doi.org/10.1137/S0097539797328847},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}