@incollection{Achlioptas-Menchaca-Mendez/12,
AUTHOR = {Achlioptas, Dimitris and Menchaca-Mendez, Ricardo},
TITLE = {Unsatisfiability bounds for random CSPs from an energetic interpolation method},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {1-12},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ada-Chattopadhyay-Fawzi-Nguyen/12,
AUTHOR = {Ada, Anil and Chattopadhyay, Arkadev and Fawzi, Omar and Nguyen, Phuong},
TITLE = {The NOF multiparty communication complexity of composed functions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {13-24},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ambainis-Backurs-Balodis-Kravcenko-Smotrovs-Virza/12,
AUTHOR = {Ambainis, Andris and Ba{\v{c}}kurs, Art{\=u}rs and Balodis, Kaspars and Krav{\v{c}}enko, Dmitrijs and Smotrovs, Raitis Ozolsand Juris and Virza, Madars},
TITLE = {Quantum strategies are better than classical in almost any XOR game},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {25-37},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Azar-Gamzu/12,
AUTHOR = {Azar, Yossi and Gamzu, Iftah},
TITLE = {Efficient submodular function maximization under linear packing constraints},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {38-50},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Babai-Codenotti-Qiao/12,
AUTHOR = {Babai, L{\'a}szl{\'o} and Codenotti, Paolo and Qiao, Youming},
TITLE = {Polynomial-time isomorphism test for groups with no Abelian normal subgroups},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {51-62},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Balcan-Liang/12,
AUTHOR = {Balcan, Maria Florina and Liang, Yingyu},
TITLE = {Clustering under perturbation resilience},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {63-74},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Barman-Umboh-Chawla-Malec/12,
AUTHOR = {Barman, Siddharth and Umboh, Seeun and Chawla, Shuchi and Malec, David},
TITLE = {Secretary problems with convex costs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {75-87},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Baron-Ostrovsky-Visconti/12,
AUTHOR = {Baron, Joshua and Ostrovsky, Rafail and Visconti, Ivan},
TITLE = {Nearly simultaneously resettable black-box zero knowledge},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {88-99},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bauwens/12,
AUTHOR = {Bauwens, Bruno},
TITLE = {Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {100-108},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bhaskara-Charikar-Manokaran-Vijayaraghavan/12,
AUTHOR = {Bhaskara, Aditya and Charikar, Moses and Manokaran, Rajsekar and Vijayaraghavan, Aravindan},
TITLE = {On quadratic programming with a ratio objective},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {109-120},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bose-Collette-Fagerberg-Langerman/12,
AUTHOR = {Bose, Prosenjit and Collette, S{\'e}bastien and Fagerberg, Rolf and Langerman, Stefan},
TITLE = {De-amortizing binary search trees},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {121-132},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bringmann-Panagiotou/12,
AUTHOR = {Bringmann, Karl and Panagiotou, Konstantinos},
TITLE = {Efficient sampling methods for discrete distributions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {133-144},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Buchbinder-Naor-Ravi-Singh/12,
AUTHOR = {Buchbinder, Niv and Naor, Joseph (Seffi) and Ravi, R. and Singh, Mohit},
TITLE = {Approximation algorithms for online weighted rank function maximization under matroid constraints},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {145-156},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Byrka-Rybicki/12,
AUTHOR = {Byrka, Jaroslaw and Rybicki, Bartosz},
TITLE = {Improved LP-rounding approximation algorithm for $k$-level uncapacitated facility location},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {157-169},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakrabarty-Huang/12,
AUTHOR = {Chakrabarty, Deeparnab and Huang, Zhiyi},
TITLE = {Testing coverage functions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {170-181},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chan-Li-Ning/12,
AUTHOR = {Chan, T.-H. Hubert and Li, Mingfei and Ning, Li},
TITLE = {Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {182-193},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Charikar-Li/12,
AUTHOR = {Charikar, Moses and Li, Shi},
TITLE = {A dependent LP-rounding approach for the $k$-median problem},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {194-205},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chekuri-Ene-Vakilian/12,
AUTHOR = {Chekuri, Chandra and Ene, Alina and Vakilian, Ali},
TITLE = {Node-weighted network design in planar and minor-closed families of graphs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {206-217},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Wang/12a,
AUTHOR = {Chen, Danny Z. and Wang, Haitao},
TITLE = {Computing the visibility polygon of an island in a polygonal domain},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {218-229},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chitnis-Cygan-Hajiaghayi-Marx/12,
AUTHOR = {Chitnis, Rajesh and Cygan, Marek and Hajiaghayi, Mohammadtaghi and Marx, D{\'a}niel},
TITLE = {Directed subset feedback vertex set is fixed-parameter tractable},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {230-241},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Crowston-Jones-Mnich/12,
AUTHOR = {Crowston, Robert and Jones, Mark and Mnich, Matthias},
TITLE = {Max-cut parameterized above the Edwards-Erd{\H{o}}s bound},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {242-253},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cygan-Kratsch-Pilipczuk-Pilipczuk-Wahlstrom/12,
AUTHOR = {Cygan, Marek and Kratsch, Stefan and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Wahlstr{\"o}m, Magnus},
TITLE = {Clique cover and graph separation: New incompressibility results},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {254-265},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{De-Diakonikolas-Servedio/12,
AUTHOR = {De, Anindya and Diakonikolas, Ilias and Servedio, Rocco},
TITLE = {The inverse Shapley value problem},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {266-277},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Deshpande-Kannan-Srivastava/12,
AUTHOR = {Deshpande, Amit and Kannan, Ravindran and Srivastava, Nikhil},
TITLE = {Zero-one rounding of singular vectors},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {278-289},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dinitz-Kortsarz-Raz/12,
AUTHOR = {Dinitz, Michael and Kortsarz, Guy and Raz, Ran},
TITLE = {Label cover instances with large girth and the hardness of approximating basic $k$-spanner},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {290-301},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Emek-Halldorsson-Rosen/12,
AUTHOR = {Emek, Yuval and Halld{\'o}rsson, Magn{\'u}s M. and Ros{\'e}n, Adi},
TITLE = {Space-constrained interval selection},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {302-313},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Etessami-Stewart-Yannakakis/12,
AUTHOR = {Etessami, Kousha and Stewart, Alistair and Yannakakis, Mihalis},
TITLE = {Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {314-326},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Farzan-Munro-Raman/12,
AUTHOR = {Farzan, Arash and Munro, J. Ian and Raman, Rajeev},
TITLE = {Succinct indices for range queries with applications to orthogonal range maxima},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {327-338},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Feige-Jozeph/12,
AUTHOR = {Feige, Uriel and Jozeph, Shlomo},
TITLE = {Universal factor graphs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {339-350},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fellows-Kulik-Rosamond-Shachnai/12,
AUTHOR = {Fellows, Michael R. and Kulik, Ariel and Rosamond, Frances and Shachnai, Hadas},
TITLE = {Parameterized approximation via fidelity preserving transformations},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {351-362},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gaspers-Szeider/12,
AUTHOR = {Gaspers, Serge and Szeider, Stefan},
TITLE = {Backdoors to acyclic SAT},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {363-374},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Georgiadis-Tarjan/12,
AUTHOR = {Georgiadis, Loukas and Tarjan, Robert E.},
TITLE = {Dominators, directed bipolar orders, and independent spanning trees},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {375-386},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gharibian-Kempe/12,
AUTHOR = {Gharibian, Sevag and Kempe, Julia},
TITLE = {Hardness of approximation for quantum problems},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {387-398},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goldberg-Jerrum/12a,
AUTHOR = {Goldberg, Leslie Ann and Jerrum, Mark},
TITLE = {The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {399-410},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gortz-Nagarajan-Saket/12,
AUTHOR = {G{\o}rtz, Inge Li and Nagarajan, Viswanath and Saket, Rishi},
TITLE = {Stochastic vehicle routing with recourse},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {411-423},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Lewi/12,
AUTHOR = {Gupta, Anupam and Lewi, Kevin},
TITLE = {The online metric matching problem for doubling metrics},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {424-435},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Nagarajan/12,
AUTHOR = {Gupta, Anupam and Nagarajan, Viswanath},
TITLE = {Approximating sparse covering integer programs online},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {436-448},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Halldorsson-Sun-Szegedy-Wang/12,
AUTHOR = {Halld{\'o}rsson, Magn{\'u}s M. and Sun, Xiaoming and Szegedy, Mario and Wang, Chengu},
TITLE = {Streaming and communication complexity of clique approximation},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {449-460},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hsu-Khanna-Roth/12,
AUTHOR = {Hsu, Justin and Khanna, Sanjeev and Roth, Aaron},
TITLE = {Distributed private heavy hitters},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {461-472},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hughes-Pavan-Russell-Selman/12,
AUTHOR = {Hughes, Andrew and Pavan, A. and Russell, Nathan and Selman, Alan},
TITLE = {A thirty year old conjecture about promise problems},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {473-484},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Im-Nagarajan-van_der_Zwaan/12,
AUTHOR = {Im, Sungjin and Nagarajan, Viswanath and van der Zwaan, Ruben},
TITLE = {Minimum latency submodular cover},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {485-497},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ito-Tanigawa-Yoshida/12,
AUTHOR = {Ito, Hiro and Tanigawa, Shin-Ichi and Yoshida, Yuichi},
TITLE = {Constant-time algorithms for sparsity matroids},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {498-509},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jansson-Sadakane-Sung/12a,
AUTHOR = {Jansson, Jesper and Sadakane, Kunihiko and Sung, Wing-Kin},
TITLE = {CRAM: Compressed random access memory},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {510-521},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jeffery-Kothari-Magniez/12,
AUTHOR = {Jeffery, Stacey and Kothari, Robin and Magniez, Fr{\'e}d{\'e}ric},
TITLE = {Improving quantum query complexity of Boolean matrix multiplication using graph collision},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {522-532},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jez/12,
AUTHOR = {Je{\.z}, Artur},
TITLE = {Faster fully compressed pattern matching by recompression},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {533-544},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kapralov-Panigrahy/12,
AUTHOR = {Kapralov, Michael and Panigrahy, Rina},
TITLE = {NNS lower bounds via metric expansion for $l_\infty$ and EMD},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {545-556},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kimmel/12,
AUTHOR = {Kimmel, Shelby},
TITLE = {Quantum adversary (upper) bound},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {557-568},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Klein-Marx/12,
AUTHOR = {Klein, Philip N. and Marx, D{\'a}niel},
TITLE = {Solving {\sc Planar} $k$-{\sc Terminal Cut} in $O(n^{c \sqrt{k}})$ time},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {569-580},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kratsch-Pilipczuk-Pilipczuk-Wahlstrom/12,
AUTHOR = {Kratsch, Stefan and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Wahlstr{\"o}m, Magnus},
TITLE = {Fixed-parameter tractability of multicut in directed acyclic graphs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {581-593},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Krauthgamer-Zondiner/12,
AUTHOR = {Krauthgamer, Robert and Zondiner, Tamar},
TITLE = {Preserving terminal distances using minors},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {594-605},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Laekhanukit-Gharan-Singh/12,
AUTHOR = {Laekhanukit, Bundit and Gharan, Shayan Oveis and Singh, Mohit},
TITLE = {A rounding by sampling approach to the minimum size $k$-arc connected subgraph problem},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {606-616},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Laplante-Lerays-Roland/12,
AUTHOR = {Laplante, Sophie and Lerays, Virginie and Roland, J{\'e}r{\'e}mie},
TITLE = {Classical and quantum partition bound and detector inefficiency},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {617-628},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Levi-Ron-Rubinfeld/12,
AUTHOR = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt},
TITLE = {Testing similar means},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {629-640},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lin-Chen/12,
AUTHOR = {Lin, Bingkai and Chen, Yijia},
TITLE = {The parameterized complexity of $k$-edge induced subgraphs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {641-652},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mansour-Rubinstein-Vardi-Xie/12,
AUTHOR = {Mansour, Yishay and Rubinstein, Aviad and Vardi, Shai and Xie, Ning},
TITLE = {Converting online algorithms to local computation algorithms},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {653-664},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Marchetti-Spaccamela-Rutten-van_der_Ster-Wiese/12,
AUTHOR = {Marchetti-Spaccamela, Alberto and Rutten, Cyriel and van der Ster, Suzanne and Wiese, Andreas},
TITLE = {Assigning sporadic tasks to unrelated parallel machines},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {665-676},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Marx/12,
AUTHOR = {Marx, D{\'a}niel},
TITLE = {A tight lower bound for planar multiway cut with fixed number of terminals},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {677-688},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Megow-Skutella-Verschae-Wiese/12,
AUTHOR = {Megow, Nicole and Skutella, Martin and Verschae, Jos{\'e} and Wiese, Andreas},
TITLE = {The power of recourse for online MST and TSP},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {689-700},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Molinaro-Ravi/12,
AUTHOR = {Molinaro, Marco and Ravi, R.},
TITLE = {Geometry of online packing linear programs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {701-713},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_59},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fu-Patitz-Schweller-Sheline/12,
AUTHOR = {Fu, Bin and Patitz, Matthew J. and Schweller, Robert T. and Sheline, Robert},
TITLE = {Self-assembly with geometric tiles},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {714-725},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Polacek-Svensson/12,
AUTHOR = {Polacek, Lukas and Svensson, Ola},
TITLE = {Quasi-polynomial local search for restricted max-min fair allocation},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {726-737},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_61},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rabin-Mansour-Muthukrishnan-Yung/12,
AUTHOR = {Rabin, Michael O. and Mansour, Yishay and Muthukrishnan, S. and Yung, Moti},
TITLE = {Strictly-black-box zero-knowledge and efficient validation of financial transactions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {738-749},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_62},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lokshtanov-Ramanujan/12,
AUTHOR = {Lokshtanov, Daniel and Ramanujan, M.S.},
TITLE = {Parameterized tractability of multiway cut with parity constraints},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {750-761},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_63},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Saha-Khuller/12,
AUTHOR = {Saha, Barna and Khuller, Samir},
TITLE = {Set cover revisited: Hypergraph cover with hard capacities},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {762-773},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_64},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Santhanam-Srinivasan/12,
AUTHOR = {Santhanam, Rahul and Srinivasan, Srikanth},
TITLE = {On the limits of sparsification},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {774-785},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_65},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schmidt/12a,
AUTHOR = {Schmidt, Jens M.},
TITLE = {Certifying 3-connectivity in linear time},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {786-797},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_66},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Shi-Wu/12,
AUTHOR = {Shi, Yaoyun and Wu, Xiaodi},
TITLE = {Epsilon-net method for optimizations over separable states},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {798-809},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_67},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Thaler-Ullman-Vadhan/12,
AUTHOR = {Thaler, Justin and Ullman, Jonathan and Vadhan, Salil},
TITLE = {Faster algorithms for privately releasing marginals},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {810-821},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_68},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Costello-Tetali-Tripathi/12,
AUTHOR = {Costello, Kevin P. and Tetali, Prasad and Tripathi, Pushkar},
TITLE = {Stochastic matching with commitment},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {822-833},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_69},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Verbin-Zhang/12,
AUTHOR = {Verbin, Elad and Zhang, Qin},
TITLE = {Rademacher-Sketch: A dimensionality-reducing embedding for sum-product norms, with an application to earth-mover distance},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {834-845},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_70},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Zouzias/12,
AUTHOR = {Zouzias, Anastasios},
TITLE = {A matrix hyperbolic cosine algorithm and applications},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part I (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7391},
PAGES = {846-858},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31594-7_71},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}