callback( { "result":{ "query":":facetid:toc:\"db/conf/focs/focs2008.bht\"", "status":{ "@code":"200", "text":"OK" }, "time":{ "@unit":"msecs", "text":"245.59" }, "completions":{ "@total":"1", "@computed":"1", "@sent":"1", "c":{ "@sc":"83", "@dc":"83", "@oc":"83", "@id":"43382449", "text":":facetid:toc:db/conf/focs/focs2008.bht" } }, "hits":{ "@total":"83", "@computed":"83", "@sent":"83", "@first":"0", "hit":[{ "@score":"1", "@id":"5346351", "info":{"authors":{"author":{"@pid":"56/1358","text":"Scott Aaronson"}},"title":"The Polynomial Method in Quantum and Classical Computing.","venue":"FOCS","pages":"3","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Aaronson08","doi":"10.1109/FOCS.2008.91","ee":"https://doi.org/10.1109/FOCS.2008.91","url":"https://dblp.org/rec/conf/focs/Aaronson08"}, "url":"URL#5346351" }, { "@score":"1", "@id":"5346352", "info":{"authors":{"author":[{"@pid":"36/5720","text":"Ittai Abraham"},{"@pid":"96/1036","text":"Yair Bartal"},{"@pid":"50/1416","text":"Ofer Neiman"}]},"title":"Nearly Tight Low Stretch Spanning Trees.","venue":"FOCS","pages":"781-790","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AbrahamBN08","doi":"10.1109/FOCS.2008.62","ee":"https://doi.org/10.1109/FOCS.2008.62","url":"https://dblp.org/rec/conf/focs/AbrahamBN08"}, "url":"URL#5346352" }, { "@score":"1", "@id":"5346353", "info":{"authors":{"author":[{"@pid":"34/4066","text":"Dimitris Achlioptas"},{"@pid":"63/522","text":"Amin Coja-Oghlan"}]},"title":"Algorithmic Barriers from Phase Transitions.","venue":"FOCS","pages":"793-802","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AchlioptasC08","doi":"10.1109/FOCS.2008.11","ee":"https://doi.org/10.1109/FOCS.2008.11","url":"https://dblp.org/rec/conf/focs/AchlioptasC08"}, "url":"URL#5346353" }, { "@score":"1", "@id":"5346354", "info":{"authors":{"author":[{"@pid":"75/3847","text":"Gagan Aggarwal"},{"@pid":"m/SMuthukrishnan","text":"S. Muthukrishnan 0001"}]},"title":"Theory of Sponsored Search Auctions.","venue":"FOCS","pages":"7","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AggarwalM08","doi":"10.1109/FOCS.2008.88","ee":"https://doi.org/10.1109/FOCS.2008.88","url":"https://dblp.org/rec/conf/focs/AggarwalM08"}, "url":"URL#5346354" }, { "@score":"1", "@id":"5346355", "info":{"authors":{"author":[{"@pid":"a/ManindraAgrawal","text":"Manindra Agrawal"},{"@pid":"77/257","text":"V. Vinay"}]},"title":"Arithmetic Circuits: A Chasm at Depth Four.","venue":"FOCS","pages":"67-75","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AgrawalV08","doi":"10.1109/FOCS.2008.32","ee":"https://doi.org/10.1109/FOCS.2008.32","url":"https://dblp.org/rec/conf/focs/AgrawalV08"}, "url":"URL#5346355" }, { "@score":"1", "@id":"5346356", "info":{"authors":{"author":[{"@pid":"a/NAlon","text":"Noga Alon"},{"@pid":"19/2179","text":"Eyal Lubetzky"},{"@pid":"s/UriStav","text":"Uri Stav"},{"@pid":"10/5870","text":"Amit Weinstein"},{"@pid":"16/2522","text":"Avinatan Hassidim"}]},"title":"Broadcasting with Side Information.","venue":"FOCS","pages":"823-832","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AlonLSWH08","doi":"10.1109/FOCS.2008.41","ee":"https://doi.org/10.1109/FOCS.2008.41","url":"https://dblp.org/rec/conf/focs/AlonLSWH08"}, "url":"URL#5346356" }, { "@score":"1", "@id":"5346357", "info":{"authors":{"author":[{"@pid":"a/NAlon","text":"Noga Alon"},{"@pid":"95/1194","text":"Asaf Nussboim"}]},"title":"k-Wise Independent Random Graphs.","venue":"FOCS","pages":"813-822","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AlonN08","doi":"10.1109/FOCS.2008.61","ee":"https://doi.org/10.1109/FOCS.2008.61","url":"https://dblp.org/rec/conf/focs/AlonN08"}, "url":"URL#5346357" }, { "@score":"1", "@id":"5346358", "info":{"authors":{"author":[{"@pid":"66/6009","text":"Alexandr Andoni"},{"@pid":"77/1357","text":"Dorian Croitoru"},{"@pid":"00/1613","text":"Mihai Patrascu"}]},"title":"Hardness of Nearest Neighbor under L-infinity.","venue":"FOCS","pages":"424-433","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AndoniCP08","doi":"10.1109/FOCS.2008.89","ee":"https://doi.org/10.1109/FOCS.2008.89","url":"https://dblp.org/rec/conf/focs/AndoniCP08"}, "url":"URL#5346358" }, { "@score":"1", "@id":"5346359", "info":{"authors":{"author":[{"@pid":"46/1698","text":"Benny Applebaum"},{"@pid":"b/BBarak","text":"Boaz Barak"},{"@pid":"53/3719","text":"David Xiao"}]},"title":"On Basing Lower-Bounds for Learning on Worst-Case Assumptions.","venue":"FOCS","pages":"211-220","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ApplebaumBX08","doi":"10.1109/FOCS.2008.35","ee":"https://doi.org/10.1109/FOCS.2008.35","url":"https://dblp.org/rec/conf/focs/ApplebaumBX08"}, "url":"URL#5346359" }, { "@score":"1", "@id":"5346360", "info":{"authors":{"author":[{"@pid":"66/5890","text":"Albert Atserias"},{"@pid":"g/MGrohe","text":"Martin Grohe"},{"@pid":"95/1832","text":"Dániel Marx"}]},"title":"Size Bounds and Query Plans for Relational Joins.","venue":"FOCS","pages":"739-748","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/AtseriasGM08","doi":"10.1109/FOCS.2008.43","ee":"https://doi.org/10.1109/FOCS.2008.43","url":"https://dblp.org/rec/conf/focs/AtseriasGM08"}, "url":"URL#5346360" }, { "@score":"1", "@id":"5346361", "info":{"authors":{"author":[{"@pid":"b/LaszloBabai","text":"László Babai"},{"@pid":"16/4087","text":"Paolo Codenotti"}]},"title":"Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time.","venue":"FOCS","pages":"667-676","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BabaiC08","doi":"10.1109/FOCS.2008.80","ee":"https://doi.org/10.1109/FOCS.2008.80","url":"https://dblp.org/rec/conf/focs/BabaiC08"}, "url":"URL#5346361" }, { "@score":"1", "@id":"5346362", "info":{"authors":{"author":[{"@pid":"b/BBarak","text":"Boaz Barak"},{"@pid":"26/4683","text":"Moritz Hardt"},{"@pid":"14/1761","text":"Ishay Haviv"},{"@pid":"63/6846","text":"Anup Rao 0001"},{"@pid":"r/OdedRegev","text":"Oded Regev 0001"},{"@pid":"59/254","text":"David Steurer"}]},"title":"Rounding Parallel Repetitions of Unique Games.","venue":"FOCS","pages":"374-383","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BarakHHRRS08","doi":"10.1109/FOCS.2008.55","ee":"https://doi.org/10.1109/FOCS.2008.55","url":"https://dblp.org/rec/conf/focs/BarakHHRRS08"}, "url":"URL#5346362" }, { "@score":"1", "@id":"5346363", "info":{"authors":{"author":[{"@pid":"b/PaulBeame","text":"Paul Beame"},{"@pid":"93/3787","text":"Dang-Trinh Huynh-Ngoc"}]},"title":"On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.","venue":"FOCS","pages":"499-508","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BeameH08","doi":"10.1109/FOCS.2008.52","ee":"https://doi.org/10.1109/FOCS.2008.52","url":"https://dblp.org/rec/conf/focs/BeameH08"}, "url":"URL#5346363" }, { "@score":"1", "@id":"5346364", "info":{"authors":{"author":[{"@pid":"82/5065","text":"Avraham Ben-Aroya"},{"@pid":"r/OdedRegev","text":"Oded Regev 0001"},{"@pid":"w/RonalddeWolf","text":"Ronald de Wolf"}]},"title":"A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs.","venue":"FOCS","pages":"477-486","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Ben-AroyaRW08","doi":"10.1109/FOCS.2008.45","ee":"https://doi.org/10.1109/FOCS.2008.45","url":"https://dblp.org/rec/conf/focs/Ben-AroyaRW08"}, "url":"URL#5346364" }, { "@score":"1", "@id":"5346365", "info":{"authors":{"author":[{"@pid":"22/6416","text":"Michael Ben-Or"},{"@pid":"16/2522","text":"Avinatan Hassidim"}]},"title":"The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well).","venue":"FOCS","pages":"221-230","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Ben-OrH08","doi":"10.1109/FOCS.2008.58","ee":"https://doi.org/10.1109/FOCS.2008.58","url":"https://dblp.org/rec/conf/focs/Ben-OrH08"}, "url":"URL#5346365" }, { "@score":"1", "@id":"5346366", "info":{"authors":{"author":[{"@pid":"22/6416","text":"Michael Ben-Or"},{"@pid":"16/2522","text":"Avinatan Hassidim"},{"@pid":"19/6178","text":"Haran Pilpel"}]},"title":"Quantum Multi Prover Interactive Proofs with Communicating Provers.","venue":"FOCS","pages":"467-476","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Ben-OrHP08","doi":"10.1109/FOCS.2008.57","ee":"https://doi.org/10.1109/FOCS.2008.57","url":"https://dblp.org/rec/conf/focs/Ben-OrHP08"}, "url":"URL#5346366" }, { "@score":"1", "@id":"5346367", "info":{"authors":{"author":[{"@pid":"02/476","text":"Eli Ben-Sasson"},{"@pid":"88/3143","text":"Jakob Nordström"}]},"title":"Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.","venue":"FOCS","pages":"709-718","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Ben-SassonN08","doi":"10.1109/FOCS.2008.42","ee":"https://doi.org/10.1109/FOCS.2008.42","url":"https://dblp.org/rec/conf/focs/Ben-SassonN08"}, "url":"URL#5346367" }, { "@score":"1", "@id":"5346368", "info":{"authors":{"author":[{"@pid":"18/3240","text":"Shankar Bhamidi"},{"@pid":"71/3436","text":"Guy Bresler"},{"@pid":"36/3231","text":"Allan Sly"}]},"title":"Mixing Time of Exponential Random Graphs.","venue":"FOCS","pages":"803-812","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BhamidiBS08","doi":"10.1109/FOCS.2008.75","ee":"https://doi.org/10.1109/FOCS.2008.75","url":"https://dblp.org/rec/conf/focs/BhamidiBS08"}, "url":"URL#5346368" }, { "@score":"1", "@id":"5346369", "info":{"authors":{"author":[{"@pid":"34/1112","text":"Punyashloka Biswal"},{"@pid":"40/837","text":"James R. Lee"},{"@pid":"r/SRao","text":"Satish Rao"}]},"title":"Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows.","venue":"FOCS","pages":"751-760","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BiswalLR08","doi":"10.1109/FOCS.2008.78","ee":"https://doi.org/10.1109/FOCS.2008.78","url":"https://dblp.org/rec/conf/focs/BiswalLR08"}, "url":"URL#5346369" }, { "@score":"1", "@id":"5346370", "info":{"authors":{"author":[{"@pid":"28/6676","text":"Andreas Björklund"},{"@pid":"71/576","text":"Thore Husfeldt"},{"@pid":"41/6988","text":"Petteri Kaski"},{"@pid":"k/MikkoKoivisto","text":"Mikko Koivisto"}]},"title":"Computing the Tutte Polynomial in Vertex-Exponential Time.","venue":"FOCS","pages":"677-686","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BjorklundHKK08","doi":"10.1109/FOCS.2008.40","ee":"https://doi.org/10.1109/FOCS.2008.40","url":"https://dblp.org/rec/conf/focs/BjorklundHKK08"}, "url":"URL#5346370" }, { "@score":"1", "@id":"5346371", "info":{"authors":{"author":[{"@pid":"b/DanBoneh","text":"Dan Boneh"},{"@pid":"46/5595","text":"Periklis A. Papakonstantinou"},{"@pid":"88/1341","text":"Charles Rackoff"},{"@pid":"96/5294","text":"Yevgeniy Vahlis"},{"@pid":"w/BrentWaters","text":"Brent Waters"}]},"title":"On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations.","venue":"FOCS","pages":"283-292","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BonehPRVW08","doi":"10.1109/FOCS.2008.67","ee":"https://doi.org/10.1109/FOCS.2008.67","url":"https://dblp.org/rec/conf/focs/BonehPRVW08"}, "url":"URL#5346371" }, { "@score":"1", "@id":"5346372", "info":{"authors":{"author":[{"@pid":"27/1509","text":"Glencora Borradaile"},{"@pid":"k/PhilipNKlein","text":"Philip N. Klein"},{"@pid":"k/ClaireKenyon","text":"Claire Mathieu"}]},"title":"A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest.","venue":"FOCS","pages":"115-124","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BorradaileKM08","doi":"10.1109/FOCS.2008.59","ee":"https://doi.org/10.1109/FOCS.2008.59","url":"https://dblp.org/rec/conf/focs/BorradaileKM08"}, "url":"URL#5346372" }, { "@score":"1", "@id":"5346373", "info":{"authors":{"author":[{"@pid":"63/5101","text":"S. Charles Brubaker"},{"@pid":"v/SantoshVempala","text":"Santosh S. Vempala"}]},"title":"Isotropic PCA and Affine-Invariant Clustering.","venue":"FOCS","pages":"551-560","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/BrubakerV08","doi":"10.1109/FOCS.2008.48","ee":"https://doi.org/10.1109/FOCS.2008.48","url":"https://dblp.org/rec/conf/focs/BrubakerV08"}, "url":"URL#5346373" }, { "@score":"1", "@id":"5346374", "info":{"authors":{"author":[{"@pid":"c/JinyiCai","text":"Jin-yi Cai"},{"@pid":"03/4112","text":"Pinyan Lu"},{"@pid":"22/4171","text":"Mingji Xia"}]},"title":"Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.","venue":"FOCS","pages":"644-653","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/CaiLX08","doi":"10.1109/FOCS.2008.34","ee":"https://doi.org/10.1109/FOCS.2008.34","url":"https://dblp.org/rec/conf/focs/CaiLX08"}, "url":"URL#5346374" }, { "@score":"1", "@id":"5346375", "info":{"authors":{"author":[{"@pid":"85/5044","text":"Amit Chakrabarti"},{"@pid":"03/3760","text":"Alexander Jaffe"},{"@pid":"40/837","text":"James R. Lee"},{"@pid":"52/64","text":"Justin Vincent"}]},"title":"Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums.","venue":"FOCS","pages":"761-770","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChakrabartiJLV08","doi":"10.1109/FOCS.2008.79","ee":"https://doi.org/10.1109/FOCS.2008.79","url":"https://dblp.org/rec/conf/focs/ChakrabartiJLV08"}, "url":"URL#5346375" }, { "@score":"1", "@id":"5346376", "info":{"authors":{"author":[{"@pid":"80/5358","text":"Deeparnab Chakrabarty"},{"@pid":"82/4256","text":"Gagan Goel"}]},"title":"On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.","venue":"FOCS","pages":"687-696","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChakrabartyG08","doi":"10.1109/FOCS.2008.47","ee":"https://doi.org/10.1109/FOCS.2008.47","url":"https://dblp.org/rec/conf/focs/ChakrabartyG08"}, "url":"URL#5346376" }, { "@score":"1", "@id":"5346377", "info":{"authors":{"author":[{"@pid":"13/2822","text":"Yuk Hei Chan"},{"@pid":"64/3360","text":"Wai Shing Fung"},{"@pid":"l/LapChiLau","text":"Lap Chi Lau"},{"@pid":"67/4920","text":"Chun Kong Yung"}]},"title":"Degree Bounded Network Design with Metric Costs.","venue":"FOCS","pages":"125-134","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChanFLY08","doi":"10.1109/FOCS.2008.28","ee":"https://doi.org/10.1109/FOCS.2008.28","url":"https://dblp.org/rec/conf/focs/ChanFLY08"}, "url":"URL#5346377" }, { "@score":"1", "@id":"5346378", "info":{"authors":{"author":[{"@pid":"63/1782","text":"Siu On Chan"},{"@pid":"m/MichaelMolloy","text":"Michael Molloy 0001"}]},"title":"A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems.","venue":"FOCS","pages":"634-643","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChanM08","doi":"10.1109/FOCS.2008.70","ee":"https://doi.org/10.1109/FOCS.2008.70","url":"https://dblp.org/rec/conf/focs/ChanM08"}, "url":"URL#5346378" }, { "@score":"1", "@id":"5346379", "info":{"authors":{"author":[{"@pid":"60/3556","text":"Timothy M. Chan"},{"@pid":"00/1613","text":"Mihai Patrascu"},{"@pid":"93/5413","text":"Liam Roditty"}]},"title":"Dynamic Connectivity: Connecting to Networks and Geometry.","venue":"FOCS","pages":"95-104","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChanPR08","doi":"10.1109/FOCS.2008.29","ee":"https://doi.org/10.1109/FOCS.2008.29","url":"https://dblp.org/rec/conf/focs/ChanPR08"}, "url":"URL#5346379" }, { "@score":"1", "@id":"5346380", "info":{"authors":{"author":[{"@pid":"06/3431","text":"Maurice Cheung"},{"@pid":"99/662","text":"Chaitanya Swamy"}]},"title":"Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply.","venue":"FOCS","pages":"35-44","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/CheungS08","doi":"10.1109/FOCS.2008.15","ee":"https://doi.org/10.1109/FOCS.2008.15","url":"https://dblp.org/rec/conf/focs/CheungS08"}, "url":"URL#5346380" }, { "@score":"1", "@id":"5346381", "info":{"authors":{"author":{"@pid":"07/5356","text":"Timothy Y. Chow"}},"title":"Almost-Natural Proofs.","venue":"FOCS","pages":"86-91","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Chow08","doi":"10.1109/FOCS.2008.16","ee":"https://doi.org/10.1109/FOCS.2008.16","url":"https://dblp.org/rec/conf/focs/Chow08"}, "url":"URL#5346381" }, { "@score":"1", "@id":"5346382", "info":{"authors":{"author":[{"@pid":"99/3386","text":"Julia Chuzhoy"},{"@pid":"k/SanjeevKhanna","text":"Sanjeev Khanna"}]},"title":"Algorithms for Single-Source Vertex Connectivity.","venue":"FOCS","pages":"105-114","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ChuzhoyK08","doi":"10.1109/FOCS.2008.63","ee":"https://doi.org/10.1109/FOCS.2008.63","url":"https://dblp.org/rec/conf/focs/ChuzhoyK08"}, "url":"URL#5346382" }, { "@score":"1", "@id":"5346383", "info":{"authors":{"author":[{"@pid":"d/ConstantinosDaskalakis","text":"Constantinos Daskalakis"},{"@pid":"p/CHPapadimitriou","text":"Christos H. Papadimitriou"}]},"title":"Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games.","venue":"FOCS","pages":"25-34","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DaskalakisP08","doi":"10.1109/FOCS.2008.84","ee":"https://doi.org/10.1109/FOCS.2008.84","url":"https://dblp.org/rec/conf/focs/DaskalakisP08"}, "url":"URL#5346383" }, { "@score":"1", "@id":"5346384", "info":{"authors":{"author":[{"@pid":"48/3493","text":"Nikhil R. Devanur"},{"@pid":"k/RaviKannan","text":"Ravi Kannan"}]},"title":"Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents.","venue":"FOCS","pages":"45-53","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DevanurK08","doi":"10.1109/FOCS.2008.30","ee":"https://doi.org/10.1109/FOCS.2008.30","url":"https://dblp.org/rec/conf/focs/DevanurK08"}, "url":"URL#5346384" }, { "@score":"1", "@id":"5346385", "info":{"authors":{"author":[{"@pid":"66/3475","text":"Peerapong Dhangwatnotai"},{"@pid":"34/917","text":"Shahar Dobzinski"},{"@pid":"54/6236","text":"Shaddin Dughmi"},{"@pid":"r/TimRoughgarden","text":"Tim Roughgarden"}]},"title":"Truthful Approximation Schemes for Single-Parameter Agents.","venue":"FOCS","pages":"15-24","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DhangwatnotaiDDR08","doi":"10.1109/FOCS.2008.71","ee":"https://doi.org/10.1109/FOCS.2008.71","url":"https://dblp.org/rec/conf/focs/DhangwatnotaiDDR08"}, "url":"URL#5346385" }, { "@score":"1", "@id":"5346386", "info":{"authors":{"author":[{"@pid":"28/1197","text":"Yefim Dinitz"},{"@pid":"19/6404","text":"Michael Elkin"},{"@pid":"s/ShaySolomon","text":"Shay Solomon"}]},"title":"Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.","venue":"FOCS","pages":"519-528","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DinitzES08","doi":"10.1109/FOCS.2008.24","ee":"https://doi.org/10.1109/FOCS.2008.24","url":"https://dblp.org/rec/conf/focs/DinitzES08"}, "url":"URL#5346386" }, { "@score":"1", "@id":"5346387", "info":{"authors":{"author":[{"@pid":"18/3891","text":"Irit Dinur"},{"@pid":"72/1836","text":"Elazar Goldenberg"}]},"title":"Locally Testing Direct Product in the Low Error Range.","venue":"FOCS","pages":"613-622","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DinurG08","doi":"10.1109/FOCS.2008.26","ee":"https://doi.org/10.1109/FOCS.2008.26","url":"https://dblp.org/rec/conf/focs/DinurG08"}, "url":"URL#5346387" }, { "@score":"1", "@id":"5346388", "info":{"authors":{"author":[{"@pid":"34/917","text":"Shahar Dobzinski"},{"@pid":"16/1346","text":"Ron Lavi"},{"@pid":"n/NoamNisan","text":"Noam Nisan"}]},"title":"Multi-unit Auctions with Budget Limits.","venue":"FOCS","pages":"260-269","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DobzinskiLN08","doi":"10.1109/FOCS.2008.39","ee":"https://doi.org/10.1109/FOCS.2008.39","url":"https://dblp.org/rec/conf/focs/DobzinskiLN08"}, "url":"URL#5346388" }, { "@score":"1", "@id":"5346389", "info":{"authors":{"author":[{"@pid":"50/2233","text":"Chinmoy Dutta"},{"@pid":"89/5476","text":"Jaikumar Radhakrishnan"}]},"title":"Lower Bounds for Noisy Wireless Networks using Sampling Algorithms.","venue":"FOCS","pages":"394-402","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DuttaR08","doi":"10.1109/FOCS.2008.72","ee":"https://doi.org/10.1109/FOCS.2008.72","url":"https://dblp.org/rec/conf/focs/DuttaR08"}, "url":"URL#5346389" }, { "@score":"1", "@id":"5346390", "info":{"authors":{"author":[{"@pid":"32/3977","text":"Zeev Dvir"},{"@pid":"w/AviWigderson","text":"Avi Wigderson"}]},"title":"Kakeya Sets, New Mergers and Old Extractors.","venue":"FOCS","pages":"625-633","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DvirW08","doi":"10.1109/FOCS.2008.23","ee":"https://doi.org/10.1109/FOCS.2008.23","url":"https://dblp.org/rec/conf/focs/DvirW08"}, "url":"URL#5346390" }, { "@score":"1", "@id":"5346391", "info":{"authors":{"author":[{"@pid":"86/5357","text":"Stefan Dziembowski"},{"@pid":"12/5020","text":"Krzysztof Pietrzak"}]},"title":"Leakage-Resilient Cryptography.","venue":"FOCS","pages":"293-302","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/DziembowskiP08","doi":"10.1109/FOCS.2008.56","ee":"https://doi.org/10.1109/FOCS.2008.56","url":"https://dblp.org/rec/conf/focs/DziembowskiP08"}, "url":"URL#5346391" }, { "@score":"1", "@id":"5346392", "info":{"authors":{"author":[{"@pid":"60/3710","text":"Matthias Englert"},{"@pid":"95/5197","text":"Deniz Özmen"},{"@pid":"w/MatthiasWestermann","text":"Matthias Westermann"}]},"title":"The Power of Reordering for Online Minimum Makespan Scheduling.","venue":"FOCS","pages":"603-612","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/EnglertOW08","doi":"10.1109/FOCS.2008.46","ee":"https://doi.org/10.1109/FOCS.2008.46","url":"https://dblp.org/rec/conf/focs/EnglertOW08"}, "url":"URL#5346392" }, { "@score":"1", "@id":"5346393", "info":{"authors":{"author":{"@pid":"11/3230","text":"Esther Ezra"}},"title":"On the Union of Cylinders in Three Dimensions.","venue":"FOCS","pages":"179-188","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Ezra08","doi":"10.1109/FOCS.2008.25","ee":"https://doi.org/10.1109/FOCS.2008.25","url":"https://dblp.org/rec/conf/focs/Ezra08"}, "url":"URL#5346393" }, { "@score":"1", "@id":"5346394", "info":{"authors":{"author":[{"@pid":"37/2407","text":"Ehud Friedgut"},{"@pid":"52/6382","text":"Gil Kalai"},{"@pid":"n/NoamNisan","text":"Noam Nisan"}]},"title":"Elections Can be Manipulated Often.","venue":"FOCS","pages":"243-249","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/FriedgutKN08","doi":"10.1109/FOCS.2008.87","ee":"https://doi.org/10.1109/FOCS.2008.87","url":"https://dblp.org/rec/conf/focs/FriedgutKN08"}, "url":"URL#5346394" }, { "@score":"1", "@id":"5346395", "info":{"authors":{"author":[{"@pid":"27/5737","text":"Zachary Friggstad"},{"@pid":"74/5082","text":"Mohammad R. Salavatipour"}]},"title":"Minimizing Movement in Mobile Facility Location Problems.","venue":"FOCS","pages":"357-366","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/FriggstadS08","doi":"10.1109/FOCS.2008.12","ee":"https://doi.org/10.1109/FOCS.2008.12","url":"https://dblp.org/rec/conf/focs/FriggstadS08"}, "url":"URL#5346395" }, { "@score":"1", "@id":"5346396", "info":{"authors":{"author":[{"@pid":"g/FGrandoni","text":"Fabrizio Grandoni 0001"},{"@pid":"27/2931","text":"Anupam Gupta 0001"},{"@pid":"l/StefanoLeonardi","text":"Stefano Leonardi 0001"},{"@pid":"05/1558","text":"Pauli Miettinen"},{"@pid":"80/4282","text":"Piotr Sankowski"},{"@pid":"21/6018","text":"Mohit Singh"}]},"title":"Set Covering with our Eyes Closed.","venue":"FOCS","pages":"347-356","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/GrandoniGLMSS08","doi":"10.1109/FOCS.2008.31","ee":"https://doi.org/10.1109/FOCS.2008.31","url":"https://dblp.org/rec/conf/focs/GrandoniGLMSS08"}, "url":"URL#5346396" }, { "@score":"1", "@id":"5346397", "info":{"authors":{"author":[{"@pid":"g/VenkatesanGuruswami","text":"Venkatesan Guruswami"},{"@pid":"94/6796","text":"Rajsekar Manokaran"},{"@pid":"69/3746","text":"Prasad Raghavendra"}]},"title":"Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.","venue":"FOCS","pages":"573-582","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/GuruswamiMR08","doi":"10.1109/FOCS.2008.51","ee":"https://doi.org/10.1109/FOCS.2008.51","url":"https://dblp.org/rec/conf/focs/GuruswamiMR08"}, "url":"URL#5346397" }, { "@score":"1", "@id":"5346398", "info":{"authors":{"author":[{"@pid":"93/4141","text":"Nicholas J. A. Harvey"},{"@pid":"68/3296","text":"Jelani Nelson"},{"@pid":"53/4305","text":"Krzysztof Onak"}]},"title":"Sketching and Streaming Entropy via Approximation Theory.","venue":"FOCS","pages":"489-498","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/HarveyNO08","doi":"10.1109/FOCS.2008.76","ee":"https://doi.org/10.1109/FOCS.2008.76","url":"https://dblp.org/rec/conf/focs/HarveyNO08"}, "url":"URL#5346398" }, { "@score":"1", "@id":"5346399", "info":{"authors":{"author":[{"@pid":"i/PiotrIndyk","text":"Piotr Indyk"},{"@pid":"54/3329","text":"Milan Ruzic"}]},"title":"Near-Optimal Sparse Recovery in the L1 Norm.","venue":"FOCS","pages":"199-207","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/IndykR08","doi":"10.1109/FOCS.2008.82","ee":"https://doi.org/10.1109/FOCS.2008.82","url":"https://dblp.org/rec/conf/focs/IndykR08"}, "url":"URL#5346399" }, { "@score":"1", "@id":"5346400", "info":{"authors":{"author":[{"@pid":"k/YaelTaumanKalai","text":"Yael Tauman Kalai"},{"@pid":"09/1365-6","text":"Xin Li 0006"},{"@pid":"63/6846","text":"Anup Rao 0001"},{"@pid":"z/DZuckerman","text":"David Zuckerman"}]},"title":"Network Extractor Protocols.","venue":"FOCS","pages":"654-663","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KalaiLRZ08","doi":"10.1109/FOCS.2008.73","ee":"https://doi.org/10.1109/FOCS.2008.73","url":"https://dblp.org/rec/conf/focs/KalaiLRZ08"}, "url":"URL#5346400" }, { "@score":"1", "@id":"5346401", "info":{"authors":{"author":[{"@pid":"52/4768","text":"Satyen Kale"},{"@pid":"31/3175","text":"Yuval Peres"},{"@pid":"60/4210","text":"C. Seshadhri 0001"}]},"title":"Noise Tolerance of Expanders and Sublinear Expander Reconstruction.","venue":"FOCS","pages":"719-728","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KalePS08","doi":"10.1109/FOCS.2008.65","ee":"https://doi.org/10.1109/FOCS.2008.65","url":"https://dblp.org/rec/conf/focs/KalePS08"}, "url":"URL#5346401" }, { "@score":"1", "@id":"5346402", "info":{"authors":{"author":[{"@pid":"67/1300","text":"Shiva Prasad Kasiviswanathan"},{"@pid":"69/288","text":"Homin K. Lee"},{"@pid":"65/801","text":"Kobbi Nissim"},{"@pid":"14/3654","text":"Sofya Raskhodnikova"},{"@pid":"04/5072","text":"Adam D. Smith"}]},"title":"What Can We Learn Privately?","venue":"FOCS","pages":"531-540","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KasiviswanathanLNRS08","doi":"10.1109/FOCS.2008.27","ee":"https://doi.org/10.1109/FOCS.2008.27","url":"https://dblp.org/rec/conf/focs/KasiviswanathanLNRS08"}, "url":"URL#5346402" }, { "@score":"1", "@id":"5346403", "info":{"authors":{"author":[{"@pid":"42/209","text":"Tali Kaufman"},{"@pid":"77/4422","text":"Shachar Lovett"}]},"title":"Worst Case to Average Case Reductions for Polynomials.","venue":"FOCS","pages":"166-175","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KaufmanL08","doi":"10.1109/FOCS.2008.17","ee":"https://doi.org/10.1109/FOCS.2008.17","url":"https://dblp.org/rec/conf/focs/KaufmanL08"}, "url":"URL#5346403" }, { "@score":"1", "@id":"5346404", "info":{"authors":{"author":[{"@pid":"45/6846","text":"Ken-ichi Kawarabayashi"},{"@pid":"08/3382","text":"Bojan Mohar"},{"@pid":"r/BruceAReed","text":"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.","venue":"FOCS","pages":"771-780","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KawarabayashiMR08","doi":"10.1109/FOCS.2008.53","ee":"https://doi.org/10.1109/FOCS.2008.53","url":"https://dblp.org/rec/conf/focs/KawarabayashiMR08"}, "url":"URL#5346404" }, { "@score":"1", "@id":"5346405", "info":{"authors":{"author":[{"@pid":"96/6462","text":"Kiran S. Kedlaya"},{"@pid":"u/ChristopherUmans","text":"Christopher Umans"}]},"title":"Fast Modular Composition in any Characteristic.","venue":"FOCS","pages":"146-155","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KedlayaU08","doi":"10.1109/FOCS.2008.13","ee":"https://doi.org/10.1109/FOCS.2008.13","url":"https://dblp.org/rec/conf/focs/KedlayaU08"}, "url":"URL#5346405" }, { "@score":"1", "@id":"5346406", "info":{"authors":{"author":[{"@pid":"k/JuliaKempe","text":"Julia Kempe"},{"@pid":"96/6151","text":"Hirotada Kobayashi"},{"@pid":"73/479","text":"Keiji Matsumoto"},{"@pid":"03/109","text":"Ben Toner"},{"@pid":"94/6173","text":"Thomas Vidick"}]},"title":"Entangled Games are Hard to Approximate.","venue":"FOCS","pages":"447-456","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KempeKMTV08","doi":"10.1109/FOCS.2008.8","ee":"https://doi.org/10.1109/FOCS.2008.8","url":"https://dblp.org/rec/conf/focs/KempeKMTV08"}, "url":"URL#5346406" }, { "@score":"1", "@id":"5346407", "info":{"authors":{"author":[{"@pid":"k/JuliaKempe","text":"Julia Kempe"},{"@pid":"r/OdedRegev","text":"Oded Regev 0001"},{"@pid":"03/109","text":"Ben Toner"}]},"title":"Unique Games with Entangled Provers are Easy.","venue":"FOCS","pages":"457-466","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KempeRT08","doi":"10.1109/FOCS.2008.9","ee":"https://doi.org/10.1109/FOCS.2008.9","url":"https://dblp.org/rec/conf/focs/KempeRT08"}, "url":"URL#5346407" }, { "@score":"1", "@id":"5346408", "info":{"authors":{"author":[{"@pid":"25/1492","text":"Subhash Khot"},{"@pid":"n/AssafNaor","text":"Assaf Naor"}]},"title":"Approximate Kernel Clustering.","venue":"FOCS","pages":"561-570","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KhotN08","doi":"10.1109/FOCS.2008.33","ee":"https://doi.org/10.1109/FOCS.2008.33","url":"https://dblp.org/rec/conf/focs/KhotN08"}, "url":"URL#5346408" }, { "@score":"1", "@id":"5346409", "info":{"authors":{"author":[{"@pid":"25/1492","text":"Subhash Khot"},{"@pid":"73/3493","text":"Rishi Saket"}]},"title":"Hardness of Minimizing and Learning DNF Expressions.","venue":"FOCS","pages":"231-240","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KhotS08","doi":"10.1109/FOCS.2008.37","ee":"https://doi.org/10.1109/FOCS.2008.37","url":"https://dblp.org/rec/conf/focs/KhotS08"}, "url":"URL#5346409" }, { "@score":"1", "@id":"5346410", "info":{"authors":{"author":[{"@pid":"39/4771","text":"Guy Kindler"},{"@pid":"34/5965","text":"Ryan O'Donnell"},{"@pid":"63/6846","text":"Anup Rao 0001"},{"@pid":"w/AviWigderson","text":"Avi Wigderson"}]},"title":"Spherical Cubes and Rounding in High Dimensions.","venue":"FOCS","pages":"189-198","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KindlerORW08","doi":"10.1109/FOCS.2008.50","ee":"https://doi.org/10.1109/FOCS.2008.50","url":"https://dblp.org/rec/conf/focs/KindlerORW08"}, "url":"URL#5346410" }, { "@score":"1", "@id":"5346411", "info":{"authors":{"author":[{"@pid":"k/AdamRKlivans","text":"Adam R. Klivans"},{"@pid":"34/5965","text":"Ryan O'Donnell"},{"@pid":"s/RAServedio","text":"Rocco A. Servedio"}]},"title":"Learning Geometric Concepts via Gaussian Surface Area.","venue":"FOCS","pages":"541-550","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/KlivansOS08","doi":"10.1109/FOCS.2008.64","ee":"https://doi.org/10.1109/FOCS.2008.64","url":"https://dblp.org/rec/conf/focs/KlivansOS08"}, "url":"URL#5346411" }, { "@score":"1", "@id":"5346412", "info":{"authors":{"author":[{"@pid":"59/6303-1","text":"Christoph Lenzen 0001"},{"@pid":"55/4247","text":"Thomas Locher"},{"@pid":"w/RogerWattenhofer","text":"Roger Wattenhofer"}]},"title":"Clock Synchronization with Bounded Global and Local Skew.","venue":"FOCS","pages":"509-518","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/LenzenLW08","doi":"10.1109/FOCS.2008.10","ee":"https://doi.org/10.1109/FOCS.2008.10","url":"https://dblp.org/rec/conf/focs/LenzenLW08"}, "url":"URL#5346412" }, { "@score":"1", "@id":"5346413", "info":{"authors":{"author":[{"@pid":"m/MonaldoMastrolilli","text":"Monaldo Mastrolilli"},{"@pid":"11/6945","text":"Ola Svensson"}]},"title":"(Acyclic) JobShops are Hard to Approximate.","venue":"FOCS","pages":"583-592","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/MastrolilliS08","doi":"10.1109/FOCS.2008.36","ee":"https://doi.org/10.1109/FOCS.2008.36","url":"https://dblp.org/rec/conf/focs/MastrolilliS08"}, "url":"URL#5346413" }, { "@score":"1", "@id":"5346414", "info":{"authors":{"author":[{"@pid":"m/JiriMatousek","text":"Jirí Matousek 0001"},{"@pid":"99/6850","text":"Anastasios Sidiropoulos"}]},"title":"Inapproximability for Metric Embeddings into Rd.","venue":"FOCS","pages":"405-413","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/MatousekS08","doi":"10.1109/FOCS.2008.21","ee":"https://doi.org/10.1109/FOCS.2008.21","url":"https://dblp.org/rec/conf/focs/MatousekS08"}, "url":"URL#5346414" }, { "@score":"1", "@id":"5346415", "info":{"authors":{"author":[{"@pid":"04/952","text":"Ankur Moitra"},{"@pid":"l/FrankThomsonLeighton","text":"Tom Leighton"}]},"title":"Some Results on Greedy Embeddings in Metric Spaces.","venue":"FOCS","pages":"337-346","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/MoitraL08","doi":"10.1109/FOCS.2008.18","ee":"https://doi.org/10.1109/FOCS.2008.18","url":"https://dblp.org/rec/conf/focs/MoitraL08"}, "url":"URL#5346415" }, { "@score":"1", "@id":"5346416", "info":{"authors":{"author":[{"@pid":"82/3753","text":"Dana Moshkovitz"},{"@pid":"91/5912","text":"Ran Raz"}]},"title":"Two Query PCP with Sub-Constant Error.","venue":"FOCS","pages":"314-323","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/MoshkovitzR08","doi":"10.1109/FOCS.2008.60","ee":"https://doi.org/10.1109/FOCS.2008.60","url":"https://dblp.org/rec/conf/focs/MoshkovitzR08"}, "url":"URL#5346416" }, { "@score":"1", "@id":"5346417", "info":{"authors":{"author":{"@pid":"m/EMossel","text":"Elchanan Mossel"}},"title":"Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes.","venue":"FOCS","pages":"156-165","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Mossel08","doi":"10.1109/FOCS.2008.44","ee":"https://doi.org/10.1109/FOCS.2008.44","url":"https://dblp.org/rec/conf/focs/Mossel08"}, "url":"URL#5346417" }, { "@score":"1", "@id":"5346418", "info":{"authors":{"author":[{"@pid":"27/1359","text":"Huy N. Nguyen"},{"@pid":"53/4305","text":"Krzysztof Onak"}]},"title":"Constant-Time Approximation Algorithms via Local Improvements.","venue":"FOCS","pages":"327-336","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/NguyenO08","doi":"10.1109/FOCS.2008.81","ee":"https://doi.org/10.1109/FOCS.2008.81","url":"https://dblp.org/rec/conf/focs/NguyenO08"}, "url":"URL#5346418" }, { "@score":"1", "@id":"5346419", "info":{"authors":{"author":[{"@pid":"p/RinaPanigrahy","text":"Rina Panigrahy"},{"@pid":"06/3696","text":"Kunal Talwar"},{"@pid":"w/UdiWieder","text":"Udi Wieder"}]},"title":"A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match.","venue":"FOCS","pages":"414-423","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/PanigrahyTW08","doi":"10.1109/FOCS.2008.68","ee":"https://doi.org/10.1109/FOCS.2008.68","url":"https://dblp.org/rec/conf/focs/PanigrahyTW08"}, "url":"URL#5346419" }, { "@score":"1", "@id":"5346420", "info":{"authors":{"author":[{"@pid":"p/CHPapadimitriou","text":"Christos H. Papadimitriou"},{"@pid":"15/5634","text":"Michael Schapira"},{"@pid":"82/4709","text":"Yaron Singer"}]},"title":"On the Hardness of Being Truthful.","venue":"FOCS","pages":"250-259","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/PapadimitriouSS08","doi":"10.1109/FOCS.2008.54","ee":"https://doi.org/10.1109/FOCS.2008.54","url":"https://dblp.org/rec/conf/focs/PapadimitriouSS08"}, "url":"URL#5346420" }, { "@score":"1", "@id":"5346421", "info":{"authors":{"author":{"@pid":"00/1613","text":"Mihai Patrascu"}},"title":"Succincter.","venue":"FOCS","pages":"305-313","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Patrascu08","doi":"10.1109/FOCS.2008.83","ee":"https://doi.org/10.1109/FOCS.2008.83","url":"https://dblp.org/rec/conf/focs/Patrascu08"}, "url":"URL#5346421" }, { "@score":"1", "@id":"5346422", "info":{"authors":{"author":{"@pid":"00/1613","text":"Mihai Patrascu"}},"title":"(Data) STRUCTURES.","venue":"FOCS","pages":"434-443","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Patrascu08a","doi":"10.1109/FOCS.2008.69","ee":"https://doi.org/10.1109/FOCS.2008.69","url":"https://dblp.org/rec/conf/focs/Patrascu08a"}, "url":"URL#5346422" }, { "@score":"1", "@id":"5346423", "info":{"authors":{"author":{"@pid":"91/5912","text":"Ran Raz"}},"title":"A Counterexample to Strong Parallel Repetition.","venue":"FOCS","pages":"369-373","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Raz08","doi":"10.1109/FOCS.2008.49","ee":"https://doi.org/10.1109/FOCS.2008.49","url":"https://dblp.org/rec/conf/focs/Raz08"}, "url":"URL#5346423" }, { "@score":"1", "@id":"5346424", "info":{"authors":{"author":[{"@pid":"91/5912","text":"Ran Raz"},{"@pid":"77/5599","text":"Amir Yehudayoff"}]},"title":"Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.","venue":"FOCS","pages":"273-282","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/RazY08","doi":"10.1109/FOCS.2008.22","ee":"https://doi.org/10.1109/FOCS.2008.22","url":"https://dblp.org/rec/conf/focs/RazY08"}, "url":"URL#5346424" }, { "@score":"1", "@id":"5346425", "info":{"authors":{"author":[{"@pid":"r/AARazborov","text":"Alexander A. Razborov"},{"@pid":"93/259","text":"Alexander A. Sherstov"}]},"title":"The Sign-Rank of ACO.","venue":"FOCS","pages":"57-66","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/RazborovS08","doi":"10.1109/FOCS.2008.19","ee":"https://doi.org/10.1109/FOCS.2008.19","url":"https://dblp.org/rec/conf/focs/RazborovS08"}, "url":"URL#5346425" }, { "@score":"1", "@id":"5346426", "info":{"authors":{"author":[{"@pid":"r/OmerReingold","text":"Omer Reingold"},{"@pid":"t/LucaTrevisan","text":"Luca Trevisan"},{"@pid":"63/5004","text":"Madhur Tulsiani"},{"@pid":"v/SPVadhan","text":"Salil P. Vadhan"}]},"title":"Dense Subsets of Pseudorandom Sets.","venue":"FOCS","pages":"76-85","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/ReingoldTTV08","doi":"10.1109/FOCS.2008.38","ee":"https://doi.org/10.1109/FOCS.2008.38","url":"https://dblp.org/rec/conf/focs/ReingoldTTV08"}, "url":"URL#5346426" }, { "@score":"1", "@id":"5346427", "info":{"authors":{"author":{"@pid":"42/5427","text":"Sébastien Roch"}},"title":"Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier.","venue":"FOCS","pages":"729-738","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Roch08","doi":"10.1109/FOCS.2008.77","ee":"https://doi.org/10.1109/FOCS.2008.77","url":"https://dblp.org/rec/conf/focs/Roch08"}, "url":"URL#5346427" }, { "@score":"1", "@id":"5346428", "info":{"authors":{"author":{"@pid":"21/1633","text":"Grant Schoenebeck"}},"title":"Linear Level Lasserre Lower Bounds for Certain k-CSPs.","venue":"FOCS","pages":"593-602","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Schoenebeck08","doi":"10.1109/FOCS.2008.74","ee":"https://doi.org/10.1109/FOCS.2008.74","url":"https://dblp.org/rec/conf/focs/Schoenebeck08"}, "url":"URL#5346428" }, { "@score":"1", "@id":"5346429", "info":{"authors":{"author":{"@pid":"93/259","text":"Alexander A. Sherstov"}},"title":"The Unbounded-Error Communication Complexity of Symmetric Functions.","venue":"FOCS","pages":"384-393","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Sherstov08","doi":"10.1109/FOCS.2008.20","ee":"https://doi.org/10.1109/FOCS.2008.20","url":"https://dblp.org/rec/conf/focs/Sherstov08"}, "url":"URL#5346429" }, { "@score":"1", "@id":"5346430", "info":{"authors":{"author":[{"@pid":"s/ZoyaSvitkina","text":"Zoya Svitkina"},{"@pid":"20/2997","text":"Lisa Fleischer"}]},"title":"Submodular Approximation: Sampling-based Algorithms and Lower Bounds.","venue":"FOCS","pages":"697-706","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/SvitkinaF08","doi":"10.1109/FOCS.2008.66","ee":"https://doi.org/10.1109/FOCS.2008.66","url":"https://dblp.org/rec/conf/focs/SvitkinaF08"}, "url":"URL#5346430" }, { "@score":"1", "@id":"5346431", "info":{"authors":{"author":{"@pid":"t/LucaTrevisan","text":"Luca Trevisan"}},"title":"Average-case Complexity.","venue":"FOCS","pages":"11","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Trevisan08","doi":"10.1109/FOCS.2008.90","ee":"https://doi.org/10.1109/FOCS.2008.90","url":"https://dblp.org/rec/conf/focs/Trevisan08"}, "url":"URL#5346431" }, { "@score":"1", "@id":"5346432", "info":{"authors":{"author":{"@pid":"y/RaphaelYuster","text":"Raphael Yuster"}},"title":"Matrix Sparsification for Rank and Determinant Computations via Nested Dissection.","venue":"FOCS","pages":"137-145","year":"2008","type":"Conference and Workshop Papers","access":"closed","key":"conf/focs/Yuster08","doi":"10.1109/FOCS.2008.14","ee":"https://doi.org/10.1109/FOCS.2008.14","url":"https://dblp.org/rec/conf/focs/Yuster08"}, "url":"URL#5346432" }, { "@score":"1", "@id":"5428133", "info":{"title":"49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA","venue":"FOCS","publisher":"IEEE Computer Society","year":"2008","type":"Editorship","key":"conf/focs/2008","ee":"https://ieeexplore.ieee.org/xpl/conhome/4690923/proceeding","url":"https://dblp.org/rec/conf/focs/2008"}, "url":"URL#5428133" } ] } } } )