| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik |
Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games.  |
FOCS  |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork |
The Promise of Differential Privacy: A Tutorial on Algorithmic Techniques. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Price, David P. Woodruff |
(1 + eps)-Approximate Sparse Recovery. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Kai-Min Chung, Rafael Pass |
The Randomness Complexity of Parallel Repetition. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph Naor, Debmalya Panigrahi, Mohit Singh |
Online Node-Weighted Steiner Tree and Related Problems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Wulff-Nilsen |
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan |
Markov Layout. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhiyi Huang, Sampath Kannan, Sanjeev Khanna |
Algorithms for the Generalized Sorting Problem. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Liam Roditty, Virginia Vassilevska Williams |
Minimum Weight Cycles and Triangles: Equivalences and Algorithms. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler |
Planar Graphs: Random Walks and Bipartiteness Testing. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy |
Quantum Query Complexity of State Conversion. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory Valiant, Paul Valiant |
The Power of Linear Estimators. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Hemanta K. Maji |
Stateless Cryptographic Protocols. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
Efficient Reconstruction of Random Multilinear Formulas. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi |
Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
Streaming Algorithms via Precision Sampling. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Alistarh, James Aspnes, Seth Gilbert, Rachid Guerraoui |
The Complexity of Renaming. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Vinod Vaikuntanathan |
Computing Blindfolded: New Developments in Fully Homomorphic Encryption. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Moran Feldman, Joseph Naor, Roy Schwartz |
A Unified Continuous Greedy Algorithm for Submodular Maximization. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Devavrat Shah, Jinwoo Shin, Prasad Tetali |
Medium Access Using Queues. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Timon Hertli |
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Shachar Lovett |
New Extension of the Weil Bound for Character Sums with Applications to Coding. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Prasad Raghavendra, David Steurer |
Rounding Semidefinite Programming Hierarchies via Global Correlation. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Ali Kemal Sinop |
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shayan Oveis Gharan, Amin Saberi, Mohit Singh |
A Randomized Rounding Approach to the Traveling Salesman Problem. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | André Chailloux, Iordanis Kerenidis |
Optimal Bounds for Quantum Bit Commitment. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor |
A Polylogarithmic-Competitive Algorithm for the k-Server Problem. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | David Bindel, Jon M. Kleinberg, Sigal Oren |
How Bad is Forming Your Own Opinion? |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yevgeniy Dodis, Allison B. Lewko, Brent Waters, Daniel Wichs |
Storing Secrets on Continually Leaky Devices. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Anup Rao |
Information Equals Amortized Communication. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Eran Omri |
Coin Flipping with Constant Bias Implies One-Way Functions. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Alina Ene |
Approximation Algorithms for Submodular Multiway Partition. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel |
Dispersers for Affine Sources with Sub-polynomial Entropy. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Blasiak, Robert Kleinberg, Eyal Lubetzky |
Lexicographic Products and the Power of Non-linear Network Coding. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ho Yee Cheung, Lap Chi Lau, Kai Man Leung |
Graph Connectivities, Network Coding, and Expander Graphs. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan |
Pseudorandomness for Read-Once Formulas. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Indyk, Eric Price, David P. Woodruff |
On the Power of Adaptivity in Sparse Recovery. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Khanna, Madhu Sudan |
Delays and the Capacity of Continuous-Time Channels. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafail Ostrovsky (eds.) |
IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011 |
FOCS |
2011 |
DBLP BibTeX RDF |
|
| 1 | Daniel Dadush, Chris Peikert, Santosh Vempala |
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang |
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail |
Near Optimal Column-Based Matrix Reconstruction. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
Extractors for Circuit Sources. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk |
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Gelles, Ankur Moitra, Amit Sahai |
Efficient and Explicit Coding for Interactive Communication. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Kirk Pruhs |
Green Computing Algorithmics. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Seth Gilbert |
Mutual Exclusion with O(log^2 Log n) Amortized Work. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder |
Balls and Bins: Smaller Hash Families and Faster Evaluation. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane |
A Small PRG for Polynomial Threshold Functions of Gaussians. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jian Li, Amol Deshpande |
Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Lior Eldar |
On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shaddin Dughmi, Jan Vondrák |
Limitations of Randomized Mechanisms for Combinatorial Auctions. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
How to Garble Arithmetic Circuits. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Muli Safra |
A Two Prover One Round Game with Strong Soundness. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma |
Welfare and Profit Maximization with Production Costs. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Shay Solomon |
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani |
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Pietro Caputo, Fabio Martinelli, Fabio Lucio Toninelli |
Sharp Mixing Time Bounds for Sampling Random Surfaces. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda |
An FPTAS for #Knapsack and Related Counting Problems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Mikkel Thorup |
The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zvika Brakerski, Vinod Vaikuntanathan |
Efficient Fully Homomorphic Encryption from (Standard) LWE. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Saeed Alaei |
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dvir Falik, Ehud Friedgut |
An Algebraic Proof of a Robust Social Choice Impossibility Theorem. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lawrence E. Blume, David A. Easley, Jon M. Kleinberg, Robert Kleinberg, Éva Tardos |
Which Networks are Least Susceptible to Cascading Failures? |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Kasper Green Larsen |
On Range Searching in the Group Model and Combinatorial Discrepancy. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
Min-max Graph Partitioning and Small Set Expansion. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman |
Privacy Amplification and Non-malleable Extractors via Character Sums. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Elad Haramaty, Amir Shpilka, Madhu Sudan |
Optimal Testing of Multivariate Polynomials over Small Prime Fields. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jing Chen, Silvio Micali |
Mechanism Design with Set-Theoretic Beliefs. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Craig Gentry, Shai Halevi |
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ioannis Koutis, Gary L. Miller, Richard Peng |
A Nearly-m log n Time Solver for SDD Linear Systems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre Fraigniaud, Amos Korman, David Peleg |
Local Distributed Decision. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandra Kolla, Konstantin Makarychev, Yury Makarychev |
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf |
Tight Lower Bounds for 2-query LCCs over Finite Fields. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen |
Near Linear Lower Bound for Dimension Reduction in L1. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Varun Kanade |
Evolution with Recombination. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Madhav Jha, Sofya Raskhodnikova |
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Madhur Tulsiani, Julia Wolf |
Quadratic Goldreich-Levin Theorems. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Jain, Penghui Yao |
A Parallel Approximation Algorithm for Positive Semidefinite Programming. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Loïc Seguin-Charbonneau, F. Bruce Shepherd |
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Surender Baswana, Manoj Gupta, Sandeep Sen |
Fully Dynamic Maximal Matching in O (log n) Update Time. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
Randomness Buys Depth for Approximate Counting. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Tobias Mömke, Ola Svensson |
Approximating Graphic TSP by Matchings. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai, Constantinos Daskalakis |
Extreme-Value Theorems for Optimal Multidimensional Pricing. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Bruce A. Reed, Paul Wollan |
The Graph Minor Algorithm with Parity Conditions. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Bonsma, Jens Schulz, Andreas Wiese |
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Wimmer |
Agnostically Learning under Permutation Invariant Distributions. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Elad Verbin |
The Coin Problem and Pseudorandomness for Branching Programs. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikhail Belkin, Kaushik Sinha |
Polynomial Learning of Distribution Families. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Awasthi, Avrim Blum, Or Sheffet |
Stability Yields a PTAS for k-Median and k-Means Clustering. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mihai Patrascu, Liam Roditty |
Distance Oracles beyond the Thorup-Zwick Bound. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, Barna Saha, Aravind Srinivasan |
New Constructive Aspects of the Lovasz Local Lemma. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Santosh Vempala |
Learning Convex Concepts from Gaussian Distributions with PCA. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal |
Constructive Algorithms for Discrepancy Minimization. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick |
All-Pairs Shortest Paths in O(n2) Time with High Probability. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Potechin |
Bounds on Monotone Switching Networks for Directed Connectivity. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Kumar, Ravindran Kannan |
Clustering with Spectral Norm and the k-Means Algorithm. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")