@article{Bar-Yehuda-Halldorsson-Naor-Shachnai-Shapira/06,
AUTHOR = {Bar-Yehuda, R. and Halld{\'o}rsson, M.M. and Naor, J.(S.) and Shachnai, H. and Shapira, I.},
TITLE = {Scheduling split intervals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {1-15},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {interval graph, independent set, scheduling, approximation algorithm},
URL = {http://link.aip.org/link/?SMJ/36/1/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bulatov-Dalmau/06,
AUTHOR = {Bulatov, Andrei and Dalmau, V{\'{i}}ctor},
TITLE = {A simple algorithm for Mal'tsev constraints},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {16-27},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {constraint satisfaction, mal'tsev},
URL = {http://link.aip.org/link/?SMJ/36/16/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Case-Jain-Martin-Sharma-Stephan/06,
AUTHOR = {Case, John and Jain, Sanjay and Martin, Eric and Sharma, Arun and Stephan, Frank},
TITLE = {Identifying clusters from positive data},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {28-55},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {inductive inference, clustering, hypothesis space, numbering, turing degree, topological and geometric properties of clusterable classes},
URL = {http://link.aip.org/link/?SMJ/36/28/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agmon-Peleg/06,
AUTHOR = {Agmon, Noa and Peleg, David},
TITLE = {Fault-tolerant gathering algorithms for autonomous mobile robots},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {56-82},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {robot swarms, autonomous mobile robots, convergence},
URL = {http://link.aip.org/link/?SMJ/36/56/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jukna/06,
AUTHOR = {Jukna, Stasys},
TITLE = {Disproving the single level conjecture},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {83-98},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {quadratic functions, monotone circuits, boolean sums, graph complexity, clique covering number, kneser graph, sylvester graph},
URL = {http://link.aip.org/link/?SMJ/36/83/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Wang-Warnow/06,
AUTHOR = {Wang, Li-San and Warnow, Tandy},
TITLE = {Reconstructing chromosomal evolution},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {99-131},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {phylogeny reconstruction, genome rearrangements, markov chain, distance correction, neighbor joining, nadeau--taylor model, inversions, transpositions},
URL = {http://link.aip.org/link/?SMJ/36/99/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Drineas-Kannan-Mahoney/06,
AUTHOR = {Drineas, Petros and Kannan, Ravi and Mahoney, Michael W.},
TITLE = {Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {132-157},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {randomized algorithms, monte carlo methods, massive data sets, streaming models, matrix multiplication},
URL = {http://link.aip.org/link/?SMJ/36/132/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Drineas-Kannan-Mahoney/06a,
AUTHOR = {Drineas, Petros and Kannan, Ravi and Mahoney, Michael W.},
TITLE = {Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {158-183},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {randomized algorithms, monte carlo methods, massive data sets, singular value decomposition},
URL = {http://link.aip.org/link/?SMJ/36/158/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Drineas-Kannan-Mahoney/06b,
AUTHOR = {Drineas, Petros and Kannan, Ravi and Mahoney, Michael W.},
TITLE = {Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {184-206},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {randomized algorithms, monte carlo methods, massive data sets, cur matrix decomposition},
URL = {http://link.aip.org/link/?SMJ/36/184/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Creignou-Zanuttini/06,
AUTHOR = {Creignou, Nadia and Zanuttini, Bruno},
TITLE = {A complete classification of the complexity of propositional abduction},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {207-229},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {abduction, propositional logic, complexity, boolean constraints},
URL = {http://link.aip.org/link/?SMJ/36/207/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feder-Hell/06,
AUTHOR = {Feder, Tomas and Hell, Pavol},
TITLE = {Full constraint satisfaction problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {230-246},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {constraint satisfaction problems, quasi-polynomial algorithms, dichotomy conjecture, conservative constraint satisfaction problems, full constraint satisfaction problems, graph homomorphisms, list homomorphisms, matrix partitions, bounded degrees, np-complete problems},
URL = {http://link.aip.org/link/?SMJ/36/230/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cryan-Dyer-Goldberg-Jerrum-Martin/06,
AUTHOR = {Cryan, Mary and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark and Martin, Russell},
TITLE = {Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {247-278},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {contingency table, balanced almost-uniform permutation, strongly balanced permutation},
URL = {http://link.aip.org/link/?SMJ/36/247/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Suzuki-Yamashita/06,
AUTHOR = {Suzuki, Ichiro and Yamashita, Masafumi},
TITLE = {Erratum to ''Distributed anonymous mobile robots: Formation of geometric patterns''},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {1},
PAGES = {279-280},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {anonymous robots, broadcast},
URL = {http://link.aip.org/link/?SMJ/36/279/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {Originally in SIAM J. Comput., Vol. 28, 1999, No. 4, 1347-1363},
}
@article{Fomin-Thilikos/06a,
AUTHOR = {Fomin, Fedor V. and Thilikos, Dimitrios M.},
TITLE = {Dominating sets in planar graphs: Branch-width and exponential speed-up},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {281-309},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {branch-width, tree-width, dominating set, planar graph, fixed-parameter algorithm},
URL = {http://link.aip.org/link/?SMJ/36/281/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kratsch-Spinrad/06,
AUTHOR = {Kratsch, Dieter and Spinrad, Jeremy},
TITLE = {Between $O(nm)$ and $O(n^\alpha)$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {310-325},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {algorithms, graphs, reductions, at-free graphs, two-pair, star cutset, dominating pair},
URL = {http://link.aip.org/link/?SMJ/36/310/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kratsch-McConnell-Mehlhorn-Spinrad/06,
AUTHOR = {Kratsch, Dieter and McConnell, Ross M. and Mehlhorn, Kurt and Spinrad, Jeremy P.},
TITLE = {Certifying algorithms for recognizing interval graphs and permutation graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {326-353},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {certificates, certifying algorithms, interval graphs, permutation graphs},
URL = {http://link.aip.org/link/?SMJ/36/326/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bartal-Fiat-Leonardi/06,
AUTHOR = {Bartal, Yair and Fiat, Amos and Leonardi, Stefano},
TITLE = {Lower bounds for on-line graph problems with application to on-line circuit and optical routing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {354-393},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {on-line computation, graph problems, network optimization, competitive analysis, randomized algorithms, lower bounds},
URL = {http://link.aip.org/link/?SMJ/36/354/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Matias-Segal-Vitter/06,
AUTHOR = {Matias, Yossi and Segal, Eran and Vitter, Jeffrey Scott},
TITLE = {Efficient bundle sorting},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {394-410},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {sorting, external memory, bundle sorting, algorithms},
URL = {http://link.aip.org/link/?SMJ/36/394/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mahdian-Ye-Zhang/06,
AUTHOR = {Mahdian, Mohammad and Ye, Yinyu and Zhang, Jiawei},
TITLE = {Approximation algorithms for metric facility location problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {411-432},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, facility location problem, greedy method, linear programming},
URL = {http://link.aip.org/link/?SMJ/36/411/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Elkin/06a,
AUTHOR = {Elkin, Michael},
TITLE = {An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {433-456},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {minimum spanning tree, distributed algorithms, hardness of approximation},
URL = {http://link.aip.org/link/?SMJ/36/433/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hoest-Shavit/06,
AUTHOR = {Hoest, Gunnar and Shavit, Nir},
TITLE = {Toward a topological characterization of asynchronous complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {457-497},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {shared memory, asynchronous systems, topology, immediate snapshots, approximate agreement, simplicial complexes, subdivisions},
URL = {http://link.aip.org/link/?SMJ/36/457/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chuzhoy-Naor/06a,
AUTHOR = {Chuzhoy, Julia and Naor, Joseph (Seffi)},
TITLE = {Covering problems with hard capacities},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {498-515},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {vertex cover, set cover, hard capacities, submodular set cover},
URL = {http://link.aip.org/link/?SMJ/36/498/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Glasser-Pavan-Selman-Sengupta/06,
AUTHOR = {Gla{\ss}er, Christian and Pavan, A. and Selman, Alan L. and Sengupta, Samik},
TITLE = {Properties of $NP$-complete sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {516-542},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {np-completeness, robustness, immunity, one-way permutations, disjoint unions},
URL = {http://link.aip.org/link/?SMJ/36/516/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feldman-Ruhl/06,
AUTHOR = {Feldman, Jon and Ruhl, Matthias},
TITLE = {The directed Steiner network problem is tractable for a constant number of terminals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {2},
PAGES = {543-561},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {steiner tree, steiner network, network design, directed graphs, polynomial-time algorithms},
URL = {http://link.aip.org/link/?SMJ/36/543/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Diehl-van_Melkebeek/06,
AUTHOR = {Diehl, Scott and van Melkebeek, Dieter},
TITLE = {Time-space lower bounds for the polynomial-time hierarchy on randomized machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {563-594},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {time-space lower bounds, randomized algorithms, polynomial-time hierarchy, satisfiability},
URL = {http://link.aip.org/link/?SMJ/36/563/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Beigel-Fortnow-Stephan/06,
AUTHOR = {Beigel, Richard and Fortnow, Lance and Stephan, Frank},
TITLE = {Infinitely-often autoreducible sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {595-608},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {algorithmic randomness, autoreducible sets, infinitely-often autoreducible sets, computational complexity, exponential-time computable sets, hausdorff-dimension},
URL = {http://link.aip.org/link/?SMJ/36/595/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Srinivasan/06,
AUTHOR = {Srinivasan, Aravind},
TITLE = {An extension of the Lov{\'a}sz local lemma, and its applications to integer programming},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {609-634},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {lovasz local lemma, column-sparse integer programs, approximation algorithms, randomized rounding, discrepancy},
URL = {http://link.aip.org/link/?SMJ/36/609/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Gao-Yu-Zang/06,
AUTHOR = {Chen, Guantao and Gao, Zhicheng and Yu, Xingxing and Zang, Wenan},
TITLE = {Approximating longest cycles in graphs with bounded degrees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {635-656},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {bounded degree, 3-connected components, long cycles, algorithm},
URL = {http://link.aip.org/link/?SMJ/36/635/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kumar-Kleinberg/06,
AUTHOR = {Kumar, Amit and Kleinberg, Jon},
TITLE = {Fairness measures for resource allocation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {657-680},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {fairness, approximation algorithms, scheduling, facility location, bandwidth allocation},
URL = {http://link.aip.org/link/?SMJ/36/657/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan/06,
AUTHOR = {Chan, Timothy M.},
TITLE = {Dynamic subgraph connectivity with geometric applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {681-694},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {data structures, dynamic graph algorithms, connectivity, computational geometry},
URL = {http://link.aip.org/link/?SMJ/36/681/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sharir-Welzl/06,
AUTHOR = {Sharir, Micha and Welzl, Emo},
TITLE = {On the number of crossing-free matchings, cycles, and partitions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {695-720},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {crossing-free geometric graphs, counting, simple polygonizations, crossing-free matchings, crossing-free partitions},
URL = {http://link.aip.org/link/?SMJ/36/695/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bronnimann-Kettner-Pocchiola-Snoeyink/06,
AUTHOR = {Br{\"o}nnimann, Herv{\'e} and Kettner, Lutz and Pocchiola, Michel and Snoeyink, Jack},
TITLE = {Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {721-739},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {algorithm, pseudotriangulation, triangulation, combinatorics, enumeration},
URL = {http://link.aip.org/link/?SMJ/36/721/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Achlioptas-Moore/06,
AUTHOR = {Achlioptas, Dimitris and Moore, Cristopher},
TITLE = {Random $k$-SAT: Two moments suffice to cross a sharp threshold},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {740-762},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {satisfiability, random formulas, phase transitions},
URL = {http://link.aip.org/link/?SMJ/36/740/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{van_Dam-Hallgren-Ip/06,
AUTHOR = {van Dam, Wim and Hallgren, Sean and Ip, Lawrence},
TITLE = {Quantum algorithms for some hidden shift problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {763-778},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum computing, efficient algorithms, legendre symbol},
URL = {http://link.aip.org/link/?SMJ/36/763/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kaufman-Ron/06,
AUTHOR = {Kaufman, Tali and Ron, Dana},
TITLE = {Testing polynomials over general fields},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {779-802},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {testing, polynomials, reedmuller codes},
URL = {http://link.aip.org/link/?SMJ/36/779/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Safra/06,
AUTHOR = {Safra, Shmuel},
TITLE = {Exponential determinization for $\omega$-automata with a strong fairness acceptance condition},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {803-814},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {omega-automata, verification, reactive systems},
URL = {http://link.aip.org/link/?SMJ/36/803/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Overmars-Sharir/06,
AUTHOR = {Agarwal, Pankaj K. and Overmars, Mark and Sharir, Micha},
TITLE = {Computing maximally separated sets in the plane},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {815-834},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {disk-intersection graphs, independent set, geometric optimization},
URL = {http://link.aip.org/link/?SMJ/36/815/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Luczak-Nesetril/06,
AUTHOR = {{\L}uczak, Tomasz and Ne{\v{s}}et{\v{r}}il, Jaroslav},
TITLE = {A probabilistic approach to the dichotomy problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {3},
PAGES = {835-843},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {csp, projectivity, random relation},
URL = {http://link.aip.org/link/?SMJ/36/835/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Applebaum-Ishai-Kushilevitz/06,
AUTHOR = {Applebaum, Benny and Ishai, Yuval and Kushilevitz, Eyal},
TITLE = {Cryptography in NC$^0$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {845-888},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {cryptography, constant depth circuits, NC$^0$ cryptographic primitives, pseudo-random generator, one-way function, randomizing polynomials},
URL = {http://link.aip.org/link/?SMJ/36/845/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
TYPE = {JOUR},
}
@article{Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan/06,
AUTHOR = {Ben-Sasson, Eli and Goldreich, Oded and Harsha, Prahladh and Sudan, Madhu and Vadhan, Salil},
TITLE = {Robust PCPs of proximity, shorter PCPs, and applications to coding},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {889-974},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {probabilistically checkable proofs, pcp, locally testable codes, locally decodable codes, property testing},
URL = {http://link.aip.org/link/?SMJ/36/889/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dinur-Reingold/06,
AUTHOR = {Dinur, Irit and Reingold, Omer},
TITLE = {Assignment testers: Towards a combinatorial proof of the PCP theorem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {975-1024},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {pcp theorem, assignment tester, combinatorial proof},
URL = {http://link.aip.org/link/?SMJ/36/975/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Khot/06a,
AUTHOR = {Khot, Subhash},
TITLE = {Ruling out PTAS for graph min-bisection, dense $k$-subgraph, and bipartite clique},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1025-1071},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {probabilistically checkable proofs (pcps), hardness of approximation, approximation algorithms},
URL = {http://link.aip.org/link/?SMJ/36/1025/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gabizon-Raz-Shaltiel/06,
AUTHOR = {Gabizon, Ariel and Raz, Ran and Shaltiel, Ronen},
TITLE = {Deterministic extractors for bit-fixing sources by obtaining an independent seed},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1072-1094},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {bit-fixing sources, deterministic extractors, derandomization, seeded extractors, seed obtainers},
URL = {http://link.aip.org/link/?SMJ/36/1072/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Barak-Impagliazzo-Wigderson/06,
AUTHOR = {Barak, Boaz and Impagliazzo, Russell and Wigderson, Avi},
TITLE = {Extracting randomness using few independent sources},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1095-1118},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {randomness extractors, ramsey graphs, sum-product theorem},
URL = {http://link.aip.org/link/?SMJ/36/1095/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bogdanov-Trevisan/06,
AUTHOR = {Bogdanov, Andrej and Trevisan, Luca},
TITLE = {On worst-case to average-case reductions for $NP$ problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1119-1159},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {average-case complexity, worst-case to average-case reduction, one-way function},
URL = {http://link.aip.org/link/?SMJ/36/1119/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vadhan/06,
AUTHOR = {Vadhan, Salil P.},
TITLE = {An unconditional study of computational zero knowledge},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1160-1214},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {cryptography, computational complexity, zero-knowledge proofs, pseudoentropy, language-dependent commitment schemes, auxiliary-input one-way functions},
URL = {http://link.aip.org/link/?SMJ/36/1160/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shpilka-Wigderson/06,
AUTHOR = {Shpilka, Amir and Wigderson, Avi},
TITLE = {Derandomizing homomorphism testing in general groups},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {4},
PAGES = {1215-1230},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {derandomization, linearity testing, homomorphism testing},
URL = {http://link.aip.org/link/?SMJ/36/1215/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kamp-Zuckerman/07,
AUTHOR = {Kamp, Jesse and Zuckerman, David},
TITLE = {Deterministic extractors for bit-fixing sources and exposure-resilient cryptography},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1231-1247},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {extractors, randomness, deterministic, bit-fixing sources, exposure-resilient, cryptography, resilient function, random walks},
URL = {http://link.aip.org/link/?SMJ/36/1231/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alekhnovich-Ben-Sasson/07,
AUTHOR = {Alekhnovich, Mikhail and Ben-Sasson, Eli},
TITLE = {Linear upper bounds for random walk on small density random 3-CNFs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1248-1263},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {sat solving, random cnf, sat heuristics, random walk algorithm},
URL = {http://link.aip.org/link/?SMJ/36/1248/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hemaspaandra-Homan-Kosub-Wagner/07,
AUTHOR = {Hemaspaandra, Lane A. and Homan, Christopher M. and Kosub, Sven and Wagner, Klaus W.},
TITLE = {The complexity of computing the size of an interval},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1264-1300},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {computational complexity, interval size functions, cluster computing, counting functions},
URL = {http://link.aip.org/link/?SMJ/36/1264/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boneh-Canetti-Halevi-Katz/07,
AUTHOR = {Boneh, Dan and Canetti, Ran and Halevi, Shai and Katz, Jonathan},
TITLE = {Chosen-ciphertext security from identity-based encryption},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1301-1328},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {identity-based encryption, public-key encryption, chosen-ciphertext security},
URL = {http://link.aip.org/link/?SMJ/36/1301/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kamidoi-Yoshida-Nagamochi/07,
AUTHOR = {Kamidoi, Yoko and Yoshida, Noriyoshi and Nagamochi, Hiroshi},
TITLE = {A deterministic algorithm for finding all minimum $k$-way cuts},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1329-1341},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {minimum cut, multiway cut, divide-and-conquer},
URL = {http://link.aip.org/link/?SMJ/36/1329/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Fiat-Kaplan-Levy-Matousek-Mossel-Pach-Sharir-Smorodinsky-Wagner-Welzl/07,
AUTHOR = {Chen, Ke and Fiat, Amos and Kaplan, Haim and Levy, Meital and Matou{\v{s}}ek, Ji{\v{r}}{\'{i}} and Mossel, Elchanan and Pach, J{\'a}nos and Sharir, Micha and Smorodinsky, Shakhar and Wagner, Uli and Welzl, Emo},
TITLE = {Online conflict-free coloring for intervals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1342-1359},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {conflict-free coloring, online algorithms, randomized algorithms, branching processes},
URL = {http://link.aip.org/link/?SMJ/36/1342/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Eppstein-Goodrich-Hirschberg/07,
AUTHOR = {Eppstein, David and Goodrich, Michael T. and Hirschberg, Daniel S.},
TITLE = {Improved combinatorial group testing algorithms for real-world problem sizes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1360-1375},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {combinatorial group testing, chinese remaindering, bloom filters},
URL = {http://link.aip.org/link/?SMJ/36/1360/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chuzhoy-Naor/07,
AUTHOR = {Chuzhoy, Julia and Naor, Joseph (Seffi)},
TITLE = {The hardness of metric labeling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1376-1386},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {metric labeling, hardness of approximation, classification},
URL = {http://link.aip.org/link/?SMJ/36/1376/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Viola/07,
AUTHOR = {Viola, Emanuele},
TITLE = {Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1387-1403},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {pseudorandom generator, derandomization, constant-depth circuit, average-case hardness, lower bound, symmetric gate, switching lemma, communication complexity},
URL = {http://link.aip.org/link/?SMJ/36/1387/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dvir-Shpilka/07,
AUTHOR = {Dvir, Zeev and Shpilka, Amir},
TITLE = {Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1404-1434},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {derandomization, polynomial identity test, arithmetic circuits, depth 3, locally decodable codes},
URL = {http://link.aip.org/link/?SMJ/36/1404/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Frieze-Sorkin/07,
AUTHOR = {Frieze, Alan and Sorkin, Gregory B.},
TITLE = {The probabilistic relationship between the assignment and asymmetric Traveling Salesman Problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1435-1452},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {assignment problem, asymmetric traveling salesman problem, average-case analysis of algorithms, random assignment problem, matching, alternating path, patching heuristic, cycle cover, permutation digraph, near-permutation digraph},
URL = {http://link.aip.org/link/?SMJ/36/1435/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chrobak-Gasieniec-Kowalski/07,
AUTHOR = {Chrobak, Marek and G{\c{a}}sieniec, Leszek and Kowalski, Dariusz R.},
TITLE = {The wake-up problem in multihop radio networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1453-1471},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {radio network, wake-up, gossiping, broadcasting, probabilistic method},
URL = {http://link.aip.org/link/?SMJ/36/1453/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Klauck-Spalek-de_Wolf/07,
AUTHOR = {Klauck, Hartmut and {\v{S}}palek, Robert and de Wolf, Ronald},
TITLE = {Quantum and classical strong direct product theorems and optimal time-space tradeoffs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1472-1493},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {complexity theory, quantum computing, lower bounds, decision trees, communication complexity},
URL = {http://link.aip.org/link/?SMJ/36/1472/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Halperin-Kortsarz-Krauthgamer-Srinivasan-Wang/07,
AUTHOR = {Halperin, Eran and Kortsarz, Guy and Krauthgamer, Robert and Srinivasan, Aravind and Wang, Nan},
TITLE = {Integrality ratio for group Steiner Trees and directed Steiner trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {5},
PAGES = {1494-1511},
YEAR = {2006-2007},
EDITOR = {Tardos, E.},
KEYWORDS = {group steiner tree, directed steiner tree, flow-based relaxation, linear programming relaxation, integrality ratio, approximation algorithms},
URL = {http://link.aip.org/link/?SMJ/36/1494/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dwork-Naor/07,
AUTHOR = {Dwork, Cynthia and Naor, Moni},
TITLE = {Zaps and their applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1513-1543},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {zero-knowledge, nonmalleable cryptosystems},
URL = {http://link.aip.org/link/?SMJ/36/1513/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Soloveichik-Winfree/07,
AUTHOR = {Soloveichik, David and Winfree, Erik},
TITLE = {Complexity of self-assembled shapes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1544-1569},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {kolmogorov complexity, scaled shapes, self-assembly, wang tiles, universal constructor},
URL = {http://link.aip.org/link/?SMJ/36/1544/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kuijpers-Kuper-Paredaens-Vandeurzen/07,
AUTHOR = {Kuijpers, Bart and Kuper, Gabriel and Paredaens, Jan and Vandeurzen, Luc},
TITLE = {First-order languages expressing constructible spatial database queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1570-1599},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {constraint databases, real algebraic geometry, first-order logic, query languages, ruler-and-compass constructions},
URL = {http://link.aip.org/link/?SMJ/36/1570/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fleischer-Skutella/07,
AUTHOR = {Fleischer, Lisa and Skutella, Martin},
TITLE = {Quickest flows over time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1600-1630},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {network flows, flows over time, dynamic flows, quickest flows, earliest arrival flows, approximation algorithms},
URL = {http://link.aip.org/link/?SMJ/36/1600/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ben-Moshe-Katz-Mitchell/07,
AUTHOR = {Ben-Moshe, Boaz and Katz, Matthew J. and Mitchell, Joseph S.B.},
TITLE = {A constant-factor approximation algorithm for optimal 1.5D terrain guarding},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1631-1647},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {geometric optimization, guarding, approximation algorithms},
URL = {http://link.aip.org/link/?SMJ/36/1631/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gabow/07,
AUTHOR = {Gabow, Harold N.},
TITLE = {Finding paths and cycles of superpolylogarithmic length},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1648-1671},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, graph algorithms, long paths, long cycles},
URL = {http://link.aip.org/link/?SMJ/36/1648/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arge-Bender-Demaine-Holland-Minkley-Munro/07,
AUTHOR = {Arge, Lars and Bender, Michael A. and Demaine, Erik D. and Holland-Minkley, Bryan and Munro, J. Ian},
TITLE = {An optimal cache-oblivious priority queue and its application to graph algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1672-1695},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {cache-oblivious algorithms, priority queue},
URL = {http://link.aip.org/link/?SMJ/36/1672/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hitchcock/07,
AUTHOR = {Hitchcock, John M.},
TITLE = {Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1696-1708},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {computational complexity, polynomial-time reductions, resource-bounded dimension, resource-bounded measure, sparse sets},
URL = {http://link.aip.org/link/?SMJ/36/1696/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chrobak-Jawor-Sgall-Tichy/07,
AUTHOR = {Chrobak, Marek and Jawor, Wojciech and Sgall, Ji{\v{r}}{\'{i}} and Tich{\'y}, Tom{\'a}{\v{s}}},
TITLE = {Online scheduling of equal-length jobs: Randomization and restarts help},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1709-1728},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {job scheduling, online algorithms, competitive analysis, randomization},
URL = {http://link.aip.org/link/?SMJ/36/1709/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schulman-Mor-Weinstein/07,
AUTHOR = {Schulman, Leonard J. and Mor, Tal and Weinstein, Yossi},
TITLE = {Physical limits of heat-bath algorithmic cooling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1729-1747},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum computation, state preparation, thermodynamics},
URL = {http://link.aip.org/link/?SMJ/36/1729/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alekseyev-Pevzner/07,
AUTHOR = {Alekseyev, Max A. and Pevzner, Pavel A.},
TITLE = {Whole genome duplications and contracted breakpoint graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1748-1763},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {genome duplication, genome halving, genome rearrangement, breakpoint graph, de bruijn graph},
URL = {http://link.aip.org/link/?SMJ/36/1748/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Varadarajan-Venkatesh-Ye-Zhang/07,
AUTHOR = {Varadarajan, Kasturi and Venkatesh, S. and Ye, Yinyu and Zhang, Jiawei},
TITLE = {Approximating the radii of point sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1764-1776},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, semidefinite programming, computational convexity},
URL = {http://link.aip.org/link/?SMJ/36/1764/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bostan-Gaudry-Schost/07,
AUTHOR = {Bostan, Alin and Gaudry, Pierrick and Schost, {\'E}ric},
TITLE = {Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator},
JOURNAL = {SIAM J. Comput.},
VOLUME = {36},
NUMBER = {6},
PAGES = {1777-1806},
YEAR = {2007},
EDITOR = {Tardos, E.},
KEYWORDS = {linear recurrences, factorization, cartiermanin operator},
URL = {http://link.aip.org/link/?SMJ/36/1777/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}