Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/focs/focs2008.bht:"
download as .bib file
@inproceedings{DBLP:conf/focs/Aaronson08,
author = {Scott Aaronson},
title = {The Polynomial Method in Quantum and Classical Computing},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {3},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.91},
doi = {10.1109/FOCS.2008.91},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Aaronson08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbrahamBN08,
author = {Ittai Abraham and
Yair Bartal and
Ofer Neiman},
title = {Nearly Tight Low Stretch Spanning Trees},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {781--790},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.62},
doi = {10.1109/FOCS.2008.62},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbrahamBN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AchlioptasC08,
author = {Dimitris Achlioptas and
Amin Coja{-}Oghlan},
title = {Algorithmic Barriers from Phase Transitions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {793--802},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.11},
doi = {10.1109/FOCS.2008.11},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AchlioptasC08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AggarwalM08,
author = {Gagan Aggarwal and
S. Muthukrishnan},
title = {Theory of Sponsored Search Auctions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {7},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.88},
doi = {10.1109/FOCS.2008.88},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AggarwalM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AgrawalV08,
author = {Manindra Agrawal and
V. Vinay},
title = {Arithmetic Circuits: {A} Chasm at Depth Four},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {67--75},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.32},
doi = {10.1109/FOCS.2008.32},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AgrawalV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonLSWH08,
author = {Noga Alon and
Eyal Lubetzky and
Uri Stav and
Amit Weinstein and
Avinatan Hassidim},
title = {Broadcasting with Side Information},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {823--832},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.41},
doi = {10.1109/FOCS.2008.41},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonLSWH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonN08,
author = {Noga Alon and
Asaf Nussboim},
title = {k-Wise Independent Random Graphs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {813--822},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.61},
doi = {10.1109/FOCS.2008.61},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AndoniCP08,
author = {Alexandr Andoni and
Dorian Croitoru and
Mihai P{u{a}}tra{c{s}}cu},
title = {Hardness of Nearest Neighbor under L-infinity},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {424--433},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.89},
doi = {10.1109/FOCS.2008.89},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AndoniCP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ApplebaumBX08,
author = {Benny Applebaum and
Boaz Barak and
David Xiao},
title = {On Basing Lower-Bounds for Learning on Worst-Case Assumptions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {211--220},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.35},
doi = {10.1109/FOCS.2008.35},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ApplebaumBX08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AtseriasGM08,
author = {Albert Atserias and
Martin Grohe and
D{\'{a}}niel Marx},
title = {Size Bounds and Query Plans for Relational Joins},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {739--748},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.43},
doi = {10.1109/FOCS.2008.43},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AtseriasGM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BabaiC08,
author = {L{\'{a}}szl{\'{o}} Babai and
Paolo Codenotti},
title = {Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {667--676},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.80},
doi = {10.1109/FOCS.2008.80},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BabaiC08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BarakHHRRS08,
author = {Boaz Barak and
Moritz Hardt and
Ishay Haviv and
Anup Rao and
Oded Regev and
David Steurer},
title = {Rounding Parallel Repetitions of Unique Games},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {374--383},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.55},
doi = {10.1109/FOCS.2008.55},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BarakHHRRS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BeameH08,
author = {Paul Beame and
Dang{-}Trinh Huynh{-}Ngoc},
title = {On the Value of Multiple Read/Write Streams for Approximating Frequency
Moments},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {499--508},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.52},
doi = {10.1109/FOCS.2008.52},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BeameH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ben-AroyaRW08,
author = {Avraham Ben{-}Aroya and
Oded Regev and
Ronald de Wolf},
title = {A Hypercontractive Inequality for Matrix-Valued Functions with Applications
to Quantum Computing and LDCs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {477--486},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.45},
doi = {10.1109/FOCS.2008.45},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ben-AroyaRW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ben-OrH08,
author = {Michael Ben{-}Or and
Avinatan Hassidim},
title = {The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty
Good for Quantum as Well)},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {221--230},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.58},
doi = {10.1109/FOCS.2008.58},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ben-OrH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ben-OrHP08,
author = {Michael Ben{-}Or and
Avinatan Hassidim and
Haran Pilpel},
title = {Quantum Multi Prover Interactive Proofs with Communicating Provers},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {467--476},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.57},
doi = {10.1109/FOCS.2008.57},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ben-OrHP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ben-SassonN08,
author = {Eli Ben{-}Sasson and
Jakob Nordstr{\"{o}}m},
title = {Short Proofs May Be Spacious: An Optimal Separation of Space and Length
in Resolution},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {709--718},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.42},
doi = {10.1109/FOCS.2008.42},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ben-SassonN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BhamidiBS08,
author = {Shankar Bhamidi and
Guy Bresler and
Allan Sly},
title = {Mixing Time of Exponential Random Graphs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {803--812},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.75},
doi = {10.1109/FOCS.2008.75},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BhamidiBS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BiswalLR08,
author = {Punyashloka Biswal and
James R. Lee and
Satish Rao},
title = {Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations
via Flows},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {751--760},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.78},
doi = {10.1109/FOCS.2008.78},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BiswalLR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BjorklundHKK08,
author = {Andreas Bj{\"{o}}rklund and
Thore Husfeldt and
Petteri Kaski and
Mikko Koivisto},
title = {Computing the Tutte Polynomial in Vertex-Exponential Time},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {677--686},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.40},
doi = {10.1109/FOCS.2008.40},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BjorklundHKK08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BonehPRVW08,
author = {Dan Boneh and
Periklis A. Papakonstantinou and
Charles Rackoff and
Yevgeniy Vahlis and
Brent Waters},
title = {On the Impossibility of Basing Identity Based Encryption on Trapdoor
Permutations},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {283--292},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.67},
doi = {10.1109/FOCS.2008.67},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BonehPRVW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BorradaileKM08,
author = {Glencora Borradaile and
Philip N. Klein and
Claire Mathieu},
title = {A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {115--124},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.59},
doi = {10.1109/FOCS.2008.59},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BorradaileKM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrubakerV08,
author = {S. Charles Brubaker and
Santosh S. Vempala},
title = {Isotropic {PCA} and Affine-Invariant Clustering},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {551--560},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.48},
doi = {10.1109/FOCS.2008.48},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrubakerV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiLX08,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms by Fibonacci Gates and Holographic Reductions
for Hardness},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {644--653},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.34},
doi = {10.1109/FOCS.2008.34},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CaiLX08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiJLV08,
author = {Amit Chakrabarti and
Alexander Jaffe and
James R. Lee and
Justin Vincent},
title = {Embeddings of Topological Graphs: Lossy Invariants, Linearization,
and 2-Sums},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {761--770},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.79},
doi = {10.1109/FOCS.2008.79},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiJLV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartyG08,
author = {Deeparnab Chakrabarty and
Gagan Goel},
title = {On the Approximability of Budgeted Allocations and Improved Lower
Bounds for Submodular Welfare Maximization and {GAP}},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {687--696},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.47},
doi = {10.1109/FOCS.2008.47},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartyG08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChanFLY08,
author = {Yuk Hei Chan and
Wai Shing Fung and
Lap Chi Lau and
Chun Kong Yung},
title = {Degree Bounded Network Design with Metric Costs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {125--134},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.28},
doi = {10.1109/FOCS.2008.28},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChanFLY08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChanM08,
author = {Siu On Chan and
Michael Molloy},
title = {A Dichotomy Theorem for the Resolution Complexity of Random Constraint
Satisfaction Problems},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {634--643},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.70},
doi = {10.1109/FOCS.2008.70},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChanM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChanPR08,
author = {Timothy M. Chan and
Mihai P{u{a}}tra{c{s}}cu and
Liam Roditty},
title = {Dynamic Connectivity: Connecting to Networks and Geometry},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {95--104},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.29},
doi = {10.1109/FOCS.2008.29},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChanPR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CheungS08,
author = {Maurice Cheung and
Chaitanya Swamy},
title = {Approximation Algorithms for Single-minded Envy-free Profit-maximization
Problems with Limited Supply},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {35--44},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.15},
doi = {10.1109/FOCS.2008.15},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CheungS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Chow08,
author = {Timothy Y. Chow},
title = {Almost-Natural Proofs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {86--91},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.16},
doi = {10.1109/FOCS.2008.16},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Chow08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChuzhoyK08,
author = {Julia Chuzhoy and
Sanjeev Khanna},
title = {Algorithms for Single-Source Vertex Connectivity},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {105--114},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.63},
doi = {10.1109/FOCS.2008.63},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChuzhoyK08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DaskalakisP08,
author = {Constantinos Daskalakis and
Christos H. Papadimitriou},
title = {Discretized Multinomial Distributions and Nash Equilibria in Anonymous
Games},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {25--34},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.84},
doi = {10.1109/FOCS.2008.84},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DaskalakisP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DevanurK08,
author = {Nikhil R. Devanur and
Ravi Kannan},
title = {Market Equilibria in Polynomial Time for Fixed Number of Goods or
Agents},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {45--53},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.30},
doi = {10.1109/FOCS.2008.30},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DevanurK08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DhangwatnotaiDDR08,
author = {Peerapong Dhangwatnotai and
Shahar Dobzinski and
Shaddin Dughmi and
Tim Roughgarden},
title = {Truthful Approximation Schemes for Single-Parameter Agents},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {15--24},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.71},
doi = {10.1109/FOCS.2008.71},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DhangwatnotaiDDR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DinitzES08,
author = {Yefim Dinitz and
Michael Elkin and
Shay Solomon},
title = {Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {519--528},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.24},
doi = {10.1109/FOCS.2008.24},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DinitzES08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DinurG08,
author = {Irit Dinur and
Elazar Goldenberg},
title = {Locally Testing Direct Product in the Low Error Range},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {613--622},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.26},
doi = {10.1109/FOCS.2008.26},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/DinurG08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DobzinskiLN08,
author = {Shahar Dobzinski and
Ron Lavi and
Noam Nisan},
title = {Multi-unit Auctions with Budget Limits},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {260--269},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.39},
doi = {10.1109/FOCS.2008.39},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DobzinskiLN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DuttaR08,
author = {Chinmoy Dutta and
Jaikumar Radhakrishnan},
title = {Lower Bounds for Noisy Wireless Networks using Sampling Algorithms},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {394--402},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.72},
doi = {10.1109/FOCS.2008.72},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DuttaR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DvirW08,
author = {Zeev Dvir and
Avi Wigderson},
title = {Kakeya Sets, New Mergers and Old Extractors},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {625--633},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.23},
doi = {10.1109/FOCS.2008.23},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DvirW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DziembowskiP08,
author = {Stefan Dziembowski and
Krzysztof Pietrzak},
title = {Leakage-Resilient Cryptography},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {293--302},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.56},
doi = {10.1109/FOCS.2008.56},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DziembowskiP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/EnglertOW08,
author = {Matthias Englert and
Deniz {\"{O}}zmen and
Matthias Westermann},
title = {The Power of Reordering for Online Minimum Makespan Scheduling},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {603--612},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.46},
doi = {10.1109/FOCS.2008.46},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/EnglertOW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ezra08,
author = {Esther Ezra},
title = {On the Union of Cylinders in Three Dimensions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {179--188},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.25},
doi = {10.1109/FOCS.2008.25},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ezra08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FriedgutKN08,
author = {Ehud Friedgut and
Gil Kalai and
Noam Nisan},
title = {Elections Can be Manipulated Often},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {243--249},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.87},
doi = {10.1109/FOCS.2008.87},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FriedgutKN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FriggstadS08,
author = {Zachary Friggstad and
Mohammad R. Salavatipour},
title = {Minimizing Movement in Mobile Facility Location Problems},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {357--366},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.12},
doi = {10.1109/FOCS.2008.12},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FriggstadS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GrandoniGLMSS08,
author = {Fabrizio Grandoni and
Anupam Gupta and
Stefano Leonardi and
Pauli Miettinen and
Piotr Sankowski and
Mohit Singh},
title = {Set Covering with our Eyes Closed},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {347--356},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.31},
doi = {10.1109/FOCS.2008.31},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GrandoniGLMSS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiMR08,
author = {Venkatesan Guruswami and
Rajsekar Manokaran and
Prasad Raghavendra},
title = {Beating the Random Ordering is Hard: Inapproximability of Maximum
Acyclic Subgraph},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {573--582},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.51},
doi = {10.1109/FOCS.2008.51},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiMR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HarveyNO08,
author = {Nicholas J. A. Harvey and
Jelani Nelson and
Krzysztof Onak},
title = {Sketching and Streaming Entropy via Approximation Theory},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {489--498},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.76},
doi = {10.1109/FOCS.2008.76},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HarveyNO08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/IndykR08,
author = {Piotr Indyk and
Milan Ruzic},
title = {Near-Optimal Sparse Recovery in the {L1} Norm},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {199--207},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.82},
doi = {10.1109/FOCS.2008.82},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/IndykR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KalaiLRZ08,
author = {Yael Tauman Kalai and
Xin Li and
Anup Rao and
David Zuckerman},
title = {Network Extractor Protocols},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {654--663},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.73},
doi = {10.1109/FOCS.2008.73},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KalaiLRZ08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KalePS08,
author = {Satyen Kale and
Yuval Peres and
C. Seshadhri},
title = {Noise Tolerance of Expanders and Sublinear Expander Reconstruction},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {719--728},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.65},
doi = {10.1109/FOCS.2008.65},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KalePS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KasiviswanathanLNRS08,
author = {Shiva Prasad Kasiviswanathan and
Homin K. Lee and
Kobbi Nissim and
Sofya Raskhodnikova and
Adam D. Smith},
title = {What Can We Learn Privately?},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {531--540},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.27},
doi = {10.1109/FOCS.2008.27},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KasiviswanathanLNRS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KaufmanL08,
author = {Tali Kaufman and
Shachar Lovett},
title = {Worst Case to Average Case Reductions for Polynomials},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {166--175},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.17},
doi = {10.1109/FOCS.2008.17},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KaufmanL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KawarabayashiMR08,
author = {Ken{-}ichi Kawarabayashi and
Bojan Mohar and
Bruce A. Reed},
title = {A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary
Surface and the Genus of Graphs of Bounded Tree-Width},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {771--780},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.53},
doi = {10.1109/FOCS.2008.53},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KawarabayashiMR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KedlayaU08,
author = {Kiran S. Kedlaya and
Christopher Umans},
title = {Fast Modular Composition in any Characteristic},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {146--155},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.13},
doi = {10.1109/FOCS.2008.13},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KedlayaU08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KempeKMTV08,
author = {Julia Kempe and
Hirotada Kobayashi and
Keiji Matsumoto and
Ben Toner and
Thomas Vidick},
title = {Entangled Games are Hard to Approximate},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {447--456},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.8},
doi = {10.1109/FOCS.2008.8},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KempeKMTV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KempeRT08,
author = {Julia Kempe and
Oded Regev and
Ben Toner},
title = {Unique Games with Entangled Provers are Easy},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {457--466},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.9},
doi = {10.1109/FOCS.2008.9},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KempeRT08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotN08,
author = {Subhash Khot and
Assaf Naor},
title = {Approximate Kernel Clustering},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {561--570},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.33},
doi = {10.1109/FOCS.2008.33},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS08,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Minimizing and Learning {DNF} Expressions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {231--240},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.37},
doi = {10.1109/FOCS.2008.37},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KindlerORW08,
author = {Guy Kindler and
Ryan O'Donnell and
Anup Rao and
Avi Wigderson},
title = {Spherical Cubes and Rounding in High Dimensions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {189--198},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.50},
doi = {10.1109/FOCS.2008.50},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KindlerORW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KlivansOS08,
author = {Adam R. Klivans and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Geometric Concepts via Gaussian Surface Area},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {541--550},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.64},
doi = {10.1109/FOCS.2008.64},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KlivansOS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LenzenLW08,
author = {Christoph Lenzen and
Thomas Locher and
Roger Wattenhofer},
title = {Clock Synchronization with Bounded Global and Local Skew},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {509--518},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.10},
doi = {10.1109/FOCS.2008.10},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LenzenLW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MastrolilliS08,
author = {Monaldo Mastrolilli and
Ola Svensson},
title = {(Acyclic) JobShops are Hard to Approximate},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {583--592},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.36},
doi = {10.1109/FOCS.2008.36},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MastrolilliS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MatousekS08,
author = {Jir{\'{\i}} Matousek and
Anastasios Sidiropoulos},
title = {Inapproximability for Metric Embeddings into Rd},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {405--413},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.21},
doi = {10.1109/FOCS.2008.21},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MatousekS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MoitraL08,
author = {Ankur Moitra and
Tom Leighton},
title = {Some Results on Greedy Embeddings in Metric Spaces},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {337--346},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.18},
doi = {10.1109/FOCS.2008.18},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MoitraL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MoshkovitzR08,
author = {Dana Moshkovitz and
Ran Raz},
title = {Two Query {PCP} with Sub-Constant Error},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {314--323},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.60},
doi = {10.1109/FOCS.2008.60},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/MoshkovitzR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Mossel08,
author = {Elchanan Mossel},
title = {Gaussian Bounds for Noise Correlation of Functions and Tight Analysis
of Long Codes},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {156--165},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.44},
doi = {10.1109/FOCS.2008.44},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Mossel08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/NguyenO08,
author = {Huy N. Nguyen and
Krzysztof Onak},
title = {Constant-Time Approximation Algorithms via Local Improvements},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {327--336},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.81},
doi = {10.1109/FOCS.2008.81},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/NguyenO08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PanigrahyTW08,
author = {Rina Panigrahy and
Kunal Talwar and
Udi Wieder},
title = {A Geometric Approach to Lower Bounds for Approximate Near-Neighbor
Search and Partial Match},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {414--423},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.68},
doi = {10.1109/FOCS.2008.68},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PanigrahyTW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PapadimitriouSS08,
author = {Christos H. Papadimitriou and
Michael Schapira and
Yaron Singer},
title = {On the Hardness of Being Truthful},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {250--259},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.54},
doi = {10.1109/FOCS.2008.54},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PapadimitriouSS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Patrascu08,
author = {Mihai P{u{a}}tra{c{s}}cu},
title = {Succincter},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {305--313},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.83},
doi = {10.1109/FOCS.2008.83},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Patrascu08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Patrascu08a,
author = {Mihai P{u{a}}tra{c{s}}cu},
title = {(Data) {STRUCTURES}},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {434--443},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.69},
doi = {10.1109/FOCS.2008.69},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Patrascu08a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Raz08,
author = {Ran Raz},
title = {A Counterexample to Strong Parallel Repetition},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {369--373},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.49},
doi = {10.1109/FOCS.2008.49},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Raz08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RazY08,
author = {Ran Raz and
Amir Yehudayoff},
title = {Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources
Extractors},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {273--282},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.22},
doi = {10.1109/FOCS.2008.22},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/RazY08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RazborovS08,
author = {Alexander A. Razborov and
Alexander A. Sherstov},
title = {The Sign-Rank of {ACO}},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {57--66},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.19},
doi = {10.1109/FOCS.2008.19},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RazborovS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ReingoldTTV08,
author = {Omer Reingold and
Luca Trevisan and
Madhur Tulsiani and
Salil P. Vadhan},
title = {Dense Subsets of Pseudorandom Sets},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {76--85},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.38},
doi = {10.1109/FOCS.2008.38},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ReingoldTTV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Roch08,
author = {S{\'{e}}bastien Roch},
title = {Sequence Length Requirement of Distance-Based Phylogeny Reconstruction:
Breaking the Polynomial Barrier},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {729--738},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.77},
doi = {10.1109/FOCS.2008.77},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Roch08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Schoenebeck08,
author = {Grant Schoenebeck},
title = {Linear Level Lasserre Lower Bounds for Certain k-CSPs},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {593--602},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.74},
doi = {10.1109/FOCS.2008.74},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Schoenebeck08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Sherstov08,
author = {Alexander A. Sherstov},
title = {The Unbounded-Error Communication Complexity of Symmetric Functions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {384--393},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.20},
doi = {10.1109/FOCS.2008.20},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Sherstov08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SvitkinaF08,
author = {Zoya Svitkina and
Lisa Fleischer},
title = {Submodular Approximation: Sampling-based Algorithms and Lower Bounds},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {697--706},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.66},
doi = {10.1109/FOCS.2008.66},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SvitkinaF08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Trevisan08,
author = {Luca Trevisan},
title = {Average-case Complexity},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {11},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.90},
doi = {10.1109/FOCS.2008.90},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Trevisan08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Yuster08,
author = {Raphael Yuster},
title = {Matrix Sparsification for Rank and Determinant Computations via Nested
Dissection},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {137--145},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.14},
doi = {10.1109/FOCS.2008.14},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Yuster08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/2008,
title = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://ieeexplore.ieee.org/xpl/conhome/4690923/proceeding},
isbn = {978-0-7695-3436-7},
timestamp = {Wed, 16 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/2008.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
retrieved on 2024-06-05 01:04 CEST from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
