| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | |
49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA   |
FOCS  |
2008 |
DBLP BibTeX RDF |
|
| 1 | Ran Raz |
A Counterexample to Strong Parallel Repetition. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Ben-Or, Avinatan Hassidim |
The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Avraham Ben-Aroya, Oded Regev, Ronald de Wolf |
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Rina Panigrahy, Kunal Talwar, Udi Wieder |
A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman |
Network Extractor Protocols. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefan Dziembowski, Krzysztof Pietrzak |
Leakage-Resilient Cryptography. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
Computing the Tutte Polynomial in Vertex-Exponential Time. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent |
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed |
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ittai Abraham, Yair Bartal, Ofer Neiman |
Nearly Tight Low Stretch Spanning Trees. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Average-case Complexity. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Shachar Lovett |
Worst Case to Average Case Reductions for Polynomials. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Shankar Bhamidi, Guy Bresler, Allan Sly |
Mixing Time of Exponential Random Graphs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Assaf Naor |
Approximate Kernel Clustering. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Amir Yehudayoff |
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | S. Charles Brubaker, Santosh Vempala |
Isotropic PCA and Affine-Invariant Clustering. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Dense Subsets of Pseudorandom Sets. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Siu On Chan, Michael Molloy |
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Satyen Kale, Yuval Peres, C. Seshadhri |
Noise Tolerance of Expanders and Sublinear Expander Reconstruction. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Monaldo Mastrolilli, Ola Svensson |
(Acyclic) JobShops are Hard to Approximate. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Punyashloka Biswal, James R. Lee, Satish Rao |
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Christoph Lenzen, Thomas Locher, Roger Wattenhofer |
Clock Synchronization with Bounded Global and Local Skew. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai, Paolo Codenotti |
Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Raphael Yuster |
Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung |
Degree Bounded Network Design with Metric Costs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Razborov, Alexander A. Sherstov |
The Sign-Rank of AC^O. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson |
Spherical Cubes and Rounding in High Dimensions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Friggstad, Mohammad R. Salavatipour |
Minimizing Movement in Mobile Facility Location Problems. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Sanjeev Khanna |
Algorithms for Single-Source Vertex Connectivity. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Elchanan Mossel |
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Maurice Cheung, Chaitanya Swamy |
Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Indyk, Milan Ruzic |
Near-Optimal Sparse Recovery in the L1 Norm. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Dorian Croitoru, Mihai Patrascu |
Hardness of Nearest Neighbor under L-infinity. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Mihai Patrascu |
(Data) STRUCTURES. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Rishi Saket |
Hardness of Minimizing and Learning DNF Expressions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Kiran S. Kedlaya, Christopher Umans |
Fast Modular Composition in any Characteristic. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, V. Vinay |
Arithmetic Circuits: A Chasm at Depth Four. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters |
On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Christos H. Papadimitriou |
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski, Ron Lavi, Noam Nisan |
Multi-unit Auctions with Budget Limits. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Sébastien Roch |
Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankur Moitra, Tom Leighton |
Some Results on Greedy Embeddings in Metric Spaces. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Dang-Trinh Huynh-Ngoc |
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Avi Wigderson |
Kakeya Sets, New Mergers and Old Extractors. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ehud Friedgut, Gil Kalai, Noam Nisan |
Elections Can be Manipulated Often. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Moshkovitz, Ran Raz |
Two Query PCP with Sub-Constant Error. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Zoya Svitkina, Lisa Fleischer |
Submodular Approximation: Sampling-based Algorithms and Lower Bounds. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, Gagan Goel |
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Boaz Barak, David Xiao |
On Basing Lower-Bounds for Learning on Worst-Case Assumptions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson |
The Polynomial Method in Quantum and Classical Computing. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Gagan Aggarwal, S. Muthukrishnan |
Theory of Sponsored Search Auctions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith |
What Can We Learn Privately? |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh |
Set Covering with our Eyes Closed. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Ben-Or, Avinatan Hassidim, Haran Pilpel |
Quantum Multi Prover Interactive Proofs with Communicating Provers. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
The Unbounded-Error Communication Complexity of Symmetric Functions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Englert, Deniz Özmen, Matthias Westermann |
The Power of Reordering for Online Minimum Makespan Scheduling. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden |
Truthful Approximation Schemes for Single-Parameter Agents. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jirí Matousek, Anastasios Sidiropoulos |
Inapproximability for Metric Embeddings into R^d. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak |
Sketching and Streaming Entropy via Approximation Theory. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yefim Dinitz, Michael Elkin, Shay Solomon |
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Ravi Kannan |
Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim |
Broadcasting with Side Information. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Jakob Nordström |
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Timothy M. Chan, Mihai Patrascu, Liam Roditty |
Dynamic Connectivity: Connecting to Networks and Geometry. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Mihai Patrascu |
Succincter. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Timothy Y. Chow |
Almost-Natural Proofs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
Learning Geometric Concepts via Gaussian Surface Area. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Elazar Goldenberg |
Locally Testing Direct Product in the Low Error Range. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dimitris Achlioptas, Amin Coja-Oghlan |
Algorithmic Barriers from Phase Transitions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Esther Ezra |
On the Union of Cylinders in Three Dimensions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Grant Schoenebeck |
Linear Level Lasserre Lower Bounds for Certain k-CSPs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer |
Rounding Parallel Repetitions of Unique Games. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos H. Papadimitriou, Michael Schapira, Yaron Singer |
On the Hardness of Being Truthful. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Chinmoy Dutta, Jaikumar Radhakrishnan |
Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Huy N. Nguyen, Krzysztof Onak |
Constant-Time Approximation Algorithms via Local Improvements. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Kempe, Oded Regev, Ben Toner |
Unique Games with Entangled Provers are Easy. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra |
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Atserias, Martin Grohe, Dániel Marx |
Size Bounds and Query Plans for Relational Joins. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Asaf Nussboim |
k-Wise Independent Random Graphs. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick |
Entangled Games are Hard to Approximate. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Terence Tao |
Structure and Randomness in Combinatorics. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | |
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings |
FOCS |
2007 |
DBLP BibTeX RDF |
|
| 1 | Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson |
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Boneh, Craig Gentry, Michael Hamburg |
Space-Efficient Identity Based Encryption Without Pairings. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov |
Inferring Local Homology from Sampled Stratified Spaces. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
Topological data analysis, local homology, stratified spaces, algorithms, Delaunay triangulations, persistence, simplicial complexes, power diagrams |
| 1 | Stefan S. Dantchev, Barnaby Martin, Stefan Szeider |
Parameterized Proof Complexity. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Muli Safra |
Hardness Amplification for Errorless Heuristics. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe |
The Power of Quantum Systems on a Line. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Louay Bazzi |
Polylogarithmic Independence Can Fool DNF Formulas. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefan Dziembowski, Krzysztof Pietrzak |
Intrusion-Resilient Secret Sharing. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Rafail Ostrovsky |
Smooth Histograms for Sliding Windows. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
Local Global Tradeoffs in Metric Embeddings. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky |
Round Complexity of Authenticated Broadcast with a Dishonest Majority. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Robert Krauthgamer |
The Computational Hardness of Estimating Edit Distance [Extended Abstract]. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Amir Shpilka, Amir Yehudayoff |
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Stefankovic, Santosh Vempala, Eric Vigoda |
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")