List of crypto (and related) conference papers of year 2012

Did you like this list? Help me to improve it by sending ideas or comments at
pcamacho at dcc dot uchile dot -NOT THIS- cl
Data gently provided by DBLP.
back to home

focs 2013

A Polynomial Time Algorithm for Lossy Population Recovery.Ankur Moitra  Michael Saks  [bibtex]
Common Information and Unique Disjointness.Gábor Braun  Sebastian Pokutta  [bibtex]
Klee's Measure Problem Made Easy.Timothy M. Chan  [bibtex]
Three-Player Entangled XOR Games Are NP-Hard to Approximate.Thomas Vidick  [bibtex]
Rational Protocol Design: Cryptography against Incentive-Driven Adversaries.Juan A. Garay  Jonathan Katz  Ueli Maurer  Björn Tackmann  Vassilis Zikas  [bibtex]
Arithmetic Circuits: A Chasm at Depth Three.Ankit Gupta 0001  Pritish Kamath  Neeraj Kayal  Ramprasad Saptharishi  [bibtex]
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy.Xin Li  [bibtex]
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.Eli Ben-Sasson  Yohay Kaplan  Swastik Kopparty  Or Meir  Henning Stichtenoth  [bibtex]
Chasing the K-Colorability Threshold.Amin Coja-Oghlan  Dan Vilenchik  [bibtex]
On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions.Natan Rubin  [bibtex]
Approximate Constraint Satisfaction Requires Large LP Relaxations.Siu On Chan  James R. Lee  Prasad Raghavendra  David Steurer  [bibtex]
The Simple Economics of Approximately Optimal Auctions.Saeed Alaei  Hu Fu  Nima Haghpanah  Jason D. Hartline  [bibtex]
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.Vitaly Feldman  Jan Vondrák  [bibtex]
Towards a Better Approximation for Sparsest Cut?Sanjeev Arora  Rong Ge  Ali Kemal Sinop  [bibtex]
Explicit Subspace Designs.Venkatesan Guruswami  Swastik Kopparty  [bibtex]
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees.Adam Marcus  Daniel A. Spielman  Nikhil Srivastava  [bibtex]
A Tight Bound for Set Disjointness in the Message-Passing Model.Mark Braverman  Faith Ellen  Rotem Oshman  Toniann Pitassi  Vinod Vaikuntanathan  [bibtex]
Fully Dynamic (1+ e)-Approximate Matchings.Manoj Gupta  Richard Peng  [bibtex]
Understanding Incentives: Mechanism Design Becomes Algorithm Design.Yang Cai  Constantinos Daskalakis  S. Matthew Weinberg  [bibtex]
How to Approximate a Set without Knowing Its Size in Advance.Rasmus Pagh  Gil Segev  Udi Wieder  [bibtex]
From Unprovability to Environmentally Friendly Protocols.Ran Canetti  Huijia Lin  Rafael Pass  [bibtex]
Approximation Schemes for Maximum Weight Independent Set of Rectangles.Anna Adamaszek  Andreas Wiese  [bibtex]
Learning Sums of Independent Integer Random Variables.Constantinos Daskalakis  Ilias Diakonikolas  Ryan O'Donnell  Rocco A. Servedio  Li-Yang Tan  [bibtex]
An O(c^k n) 5-Approximation Algorithm for Treewidth.Hans L. Bodlaender  Pål Grønås Drange  Markus S. Dregi  Fedor V. Fomin  Daniel Lokshtanov  Michal Pilipczuk  [bibtex]
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search.Marek Cygan  [bibtex]
Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors.Harold N. Gabow  Piotr Sankowski  [bibtex]
Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture.Hing Yin Tsang  Chung Hoi Wong  Ning Xie  Shengyu Zhang  [bibtex]
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.Jochen Könemann  Sina Sadeghian Sadeghabad  Laura Sanità  [bibtex]
Online Node-Weighted Steiner Forest and Extensions via Disk Paintings.Mohammad Taghi Hajiaghayi  Vahid Liaghat  Debmalya Panigrahi  [bibtex]
Strong LTCs with Inverse Poly-Log Rate and Constant Soundness.Michael Viderman  [bibtex]
The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant.Vittorio Bilò  Michele Flammini  Luca Moscardelli  [bibtex]
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity.Venkatesan Guruswami  Patrick Xia  [bibtex]
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.Marek Cygan  Dániel Marx  Marcin Pilipczuk  Michal Pilipczuk  [bibtex]
An Improved Competitive Algorithm for Reordering Buffer Management.Noa Avigdor-Elgrabli  Yuval Rabani  [bibtex]
A Linear Time Approximation Scheme for Euclidean TSP.Yair Bartal  Lee-Ad Gottlieb  [bibtex]
Approximation Algorithms for Euler Genus and Related Problems.Chandra Chekuri  Anastasios Sidiropoulos  [bibtex]
Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant.Alistair Sinclair  Piyush Srivastava  Yitong Yin  [bibtex]
Constant-Round Concurrent Zero Knowledge from P-Certificates.Kai-Min Chung  Huijia Lin  Rafael Pass  [bibtex]
Average Case Lower Bounds for Monotone Switching Networks.Yuval Filmus  Toniann Pitassi  Robert Robere  Stephen A. Cook  [bibtex]
Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back.Aleksander Madry  [bibtex]
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.Parinya Chalermsook  Bundit Laekhanukit  Danupon Nanongkai  [bibtex]
Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence.Mikkel Thorup  [bibtex]
Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits.Sanjam Garg  Craig Gentry  Shai Halevi  Mariana Raykova 0001  Amit Sahai  Brent Waters  [bibtex]
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs.Michael A. Forbes  Amir Shpilka  [bibtex]
On Clustering Induced Voronoi Diagrams.Danny Z. Chen  Ziyun Huang  Yangwei Liu  Jinhui Xu  [bibtex]
Approximating Minimization Diagrams and Generalized Proximity Search.Sariel Har-Peled  Nirman Kumar  [bibtex]
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems.Mert Saglam  Gábor Tardos  [bibtex]
The Complexity of Approximating Vertex Expansion.Anand Louis  Prasad Raghavendra  Santosh Vempala  [bibtex]
Adaptive Seeding in Social Networks.Lior Seeman  Yaron Singer  [bibtex]
The Parity of Directed Hamiltonian Cycles.Andreas Björklund  Thore Husfeldt  [bibtex]
Bandits with Knapsacks.Ashwinkumar Badanidiyuru  Robert Kleinberg  Aleksandrs Slivkins  [bibtex]
Knowledge-Preserving Interactive Coding.Kai-Min Chung  Rafael Pass  Sidharth Telang  [bibtex]
A Forward-Backward Single-Source Shortest Paths Algorithm.David B. Wilson 0002  Uri Zwick  [bibtex]
Strong Backdoors to Bounded Treewidth SAT.Serge Gaspers  Stefan Szeider  [bibtex]
Estimating the Distance from Testable Affine-Invariant Properties.Hamed Hatami  Shachar Lovett  [bibtex]
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.Monika Henzinger  Sebastian Krinninger  Danupon Nanongkai  [bibtex]
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs.Joseph Cheriyan  László A. Végh  [bibtex]
PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring.Irit Dinur  Venkatesan Guruswami  [bibtex]
Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring.Vida Dujmovic  Pat Morin  David R. Wood  [bibtex]
The Moser-Tardos Framework with Partial Resampling.David G. Harris  Aravind Srinivasan  [bibtex]
Improved Average-Case Lower Bounds for DeMorgan Formula Size.Ilan Komargodski  Ran Raz  Avishay Tal  [bibtex]
Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy.Raef Bassily  Adam Groce  Jonathan Katz  Adam Smith  [bibtex]
On Randomized Memoryless Algorithms for the Weighted K-Server Problem.Ashish Chiplunkar  Sundar Vishwanathan  [bibtex]
Iterative Row Sampling.Mu Li  Gary L. Miller  Richard Peng  [bibtex]
Direct Products in Communication Complexity.Mark Braverman  Anup Rao  Omri Weinstein  Amir Yehudayoff  [bibtex]
Quantum 3-SAT Is QMA1-Complete.David Gosset  Daniel Nagaj  [bibtex]
Non-positive Curvature and the Planar Embedding Conjecture.Anastasios Sidiropoulos  [bibtex]
Local Privacy and Statistical Minimax Rates.John C. Duchi  Michael I. Jordan  Martin J. Wainwright  [bibtex]
Faster Canonical Forms for Strongly Regular Graphs.László Babai  Xi Chen  Xiaorui Sun  Shang-Hua Teng  John Wilmes  [bibtex]
Element Distinctness, Frequency Moments, and Sliding Windows.Paul Beame  Raphaël Clifford  Widad Machmouchi  [bibtex]
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.Yin Tat Lee  Aaron Sidford  [bibtex]
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers.Andrew Drucker  [bibtex]
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.Russell Impagliazzo  Ramamohan Paturi  Stefan Schneider  [bibtex]
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings.Jelani Nelson  Huy L. Nguyên  [bibtex]
Playing Non-linear Games with Linear Oracles.Dan Garber  Elad Hazan  [bibtex]
Simultaneous Resettability from One-Way Functions.Kai-Min Chung  Rafail Ostrovsky  Rafael Pass  Ivan Visconti  [bibtex]
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins.Thomas Rothvoß  [bibtex]
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs.Ken-ichi Kawarabayashi  Yusuke Kobayashi  [bibtex]
Nearly Maximum Flows in Nearly Linear Time.Jonah Sherman  [bibtex]

stoc 2013

Quasipolynomial-time canonical form for steiner designs.László Babai  John Wilmes  [bibtex]
The complexity of finite-valued CSPs.Johan Thapper  Stanislav Zivny  [bibtex]
Approximation resistance from pairwise independent subgroups.Siu On Chan  [bibtex]
Coevolutionary opinion formation games.Kshipra Bhawalkar  Sreenivas Gollapudi  Kamesh Munagala  [bibtex]
On the complexity of trial and error.Xiaohui Bei  Ning Chen  Shengyu Zhang  [bibtex]
Classical hardness of learning with errors.Zvika Brakerski  Adeline Langlois  Chris Peikert  Oded Regev  Damien Stehlé  [bibtex]
Simplex partitioning via exponential clocks and the multiway cut problem.Niv Buchbinder  Joseph Naor  Roy Schwartz  [bibtex]
Low rank approximation and regression in input sparsity time.Kenneth L. Clarkson  David P. Woodruff  [bibtex]
The loss of serving in the dark.Yossi Azar  Ilan Reuven Cohen  Iftah Gamzu  [bibtex]
Non-black-box simulation from one-way functions and applications to resettable security.Kai-Min Chung  Rafael Pass  Karn Seth  [bibtex]
Differential privacy for the analyst via private equilibrium computation.Justin Hsu  Aaron Roth  Jonathan Ullman  [bibtex]
Some trade-off results for polynomial calculus: extended abstract.Chris Beck  Jakob Nordström  Bangsheng Tang  [bibtex]
New independent source extractors with exponential improvement.Xin Li  [bibtex]
Interactive channel capacity.Gillat Kol  Ran Raz  [bibtex]
The orbit problem in higher dimensions.Ventsislav Chonev  Joël Ouaknine  James Worrell  [bibtex]
Reusable garbled circuits and succinct functional encryption.Shafi Goldwasser  Yael Tauman Kalai  Raluca A. Popa  Vinod Vaikuntanathan  Nickolai Zeldovich  [bibtex]
Answering n{2+o(1)} counting queries with differential privacy is hard.Jonathan Ullman  [bibtex]
Tight bounds for online vector bin packing.Yossi Azar  Ilan Reuven Cohen  Seny Kamara  Bruce Shepherd  [bibtex]
Succinct sampling from discrete distributions.Karl Bringmann  Kasper Green Larsen  [bibtex]
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract].Aaron Bernstein  [bibtex]
A o(n) monotonicity tester for boolean functions over the hypercube.Deeparnab Chakrabarty  C. Seshadhri  [bibtex]
Beyond worst-case analysis in private singular vector computation.Moritz Hardt  Aaron Roth  [bibtex]
A node-capacitated okamura-seymour theorem.James R. Lee  Manor Mendel  Mohammad Moharrami  [bibtex]
The geometry of differential privacy: the sparse and approximate cases.Aleksandar Nikolov  Kunal Talwar  Li Zhang 0001  [bibtex]
Delegation for bounded space.Yael Tauman Kalai  Ran Raz  Ron D. Rothblum  [bibtex]
Approximating k-median via pseudo-approximation.Shi Li  Ola Svensson  [bibtex]
Testing subdivision-freeness: property testing meets structural graph theory.Ken-ichi Kawarabayashi  Yuichi Yoshida  [bibtex]
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems.Xi Chen  Xiaorui Sun  Shang-Hua Teng  [bibtex]
Average-case lower bounds for formula size.Ilan Komargodski  Ran Raz  [bibtex]
Tatonnement beyond gross substitutes?: gradient descent to the rescue.Yun Kuen Cheung  Richard Cole  Nikhil R. Devanur  [bibtex]
A new family of locally correctable codes based on degree-lifted algebraic geometry codes.Eli Ben-Sasson  Ariel Gabizon  Yohay Kaplan  Swastik Kopparty  Shubhangi Saraf  [bibtex]
Lee-Yang theorems and the complexity of computing averages.Alistair Sinclair  Piyush Srivastava  [bibtex]
Inverting well conditioned matrices in quantum logspace.Amnon Ta-Shma  [bibtex]
Composable and efficient mechanisms.Vasilis Syrgkanis  Éva Tardos  [bibtex]
On the concrete efficiency of probabilistically-checkable proofs.Eli Ben-Sasson  Alessandro Chiesa  Daniel Genkin  Eran Tromer  [bibtex]
Fast approximation algorithms for the diameter and radius of sparse graphs.Liam Roditty  Virginia Vassilevska Williams  [bibtex]
Recursive composition and bootstrapping for SNARKS and proof-carrying data.Nir Bitansky  Ran Canetti  Alessandro Chiesa  Eran Tromer  [bibtex]
Witness encryption and its applications.Sanjam Garg  Craig Gentry  Amit Sahai  Brent Waters  [bibtex]
An information complexity approach to extended formulations.Mark Braverman  Ankur Moitra  [bibtex]
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.Deeparnab Chakrabarty  C. Seshadhri  [bibtex]
Non-black-box simulation in the fully concurrent setting.Vipul Goyal  [bibtex]
Simultaneous auctions are (almost) efficient.Michal Feldman  Hu Fu  Nick Gravin  Brendan Lucier  [bibtex]
Communication lower bounds using directional derivatives.Alexander A. Sherstov  [bibtex]
Byzantine agreement in polynomial expected time: [extended abstract].Valerie King  Jared Saia  [bibtex]
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression.Xiangrui Meng  Michael W. Mahoney  [bibtex]
Max flows in O(nm) time, or better.James B. Orlin  [bibtex]
Solving large optimization problems using spectral graph theory.Gary L. Miller  [bibtex]
Fast hamiltonicity checking via bases of perfect matchings.Marek Cygan  Stefan Kratsch  Jesper Nederlof  [bibtex]
Explicit lower bounds via geometric complexity theory.Peter Bürgisser  Christian Ikenmeyer  [bibtex]
The complexity of non-monotone markets.Xi Chen  Dimitris Paparas  Mihalis Yannakakis  [bibtex]
Going after the k-SAT threshold.Amin Coja-Oghlan  Konstantinos Panagiotou  [bibtex]
Lower bounds for RAMs and quantifier elimination.Miklós Ajtai  [bibtex]
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound.Venkatesan Guruswami  Chaoping Xing  [bibtex]
On the list decodability of random linear codes with large error rates.Mary Wootters  [bibtex]
Low-rank matrix completion using alternating minimization.Prateek Jain 0002  Praneeth Netrapalli  Sujay Sanghavi  [bibtex]
Simple deterministic algorithms for fully dynamic maximal matching.Ofer Neiman  Shay Solomon  [bibtex]
Statistical algorithms and a lower bound for detecting planted cliques.Vitaly Feldman  Elena Grigorescu  Lev Reyzin  Santosh Vempala  Ying Xiao  [bibtex]
Bottom-k and priority sampling, set similarity and subset sums with minimal independence.Mikkel Thorup  [bibtex]
Polynomial-time perfect matchings in dense hypergraphs.Peter Keevash  Fiachra Knox  Richard Mycroft  [bibtex]
From information to exact communication.Mark Braverman  Ankit Garg  Denis Pankratov  Omri Weinstein  [bibtex]
Equivalence of deterministic one-counter automata is NL-complete.Stanislav Böhm  Stefan Göller  Petr Jancar  [bibtex]
A complete dichotomy rises from the capture of vanishing signatures: extended abstract.Jin-yi Cai  Heng Guo  Tyson Williams  [bibtex]
Optimal euclidean spanners: really short, thin and lanky.Michael Elkin  Shay Solomon  [bibtex]
New bounds for matching vector families.Abhishek Bhowmick  Zeev Dvir  Shachar Lovett  [bibtex]
The power of deferral: maintaining a constant-competitive steiner tree online.Albert Gu  Anupam Gupta  Amit Kumar 0001  [bibtex]
Stochastic combinatorial optimization via poisson approximation.Jian Li  Wen Yuan  [bibtex]
How robust are linear sketches to adaptive inputs?Moritz Hardt  David P. Woodruff  [bibtex]
Product-state approximations to quantum ground states.Fernando G. S. L. Brandão  Aram Wettroth Harrow  [bibtex]
Combinatorial walrasian equilibrium.Michal Feldman  Nick Gravin  Brendan Lucier  [bibtex]
Efficient rounding for the noncommutative grothendieck inequality.Assaf Naor  Oded Regev  Thomas Vidick  [bibtex]
Strong ETH holds for regular resolution.Christopher Beck  Russell Impagliazzo  [bibtex]
Majority is stablest: discrete and SoS.Anindya De  Elchanan Mossel  Joe Neeman  [bibtex]
On the impossibility of approximate obfuscation and applications to resettable cryptography.Nir Bitansky  Omer Paneth  [bibtex]
Every locally characterized affine-invariant property is testable.Arnab Bhattacharyya  Eldar Fischer  Hamed Hatami  Pooya Hatami  Shachar Lovett  [bibtex]
Structured recursive separator decompositions for planar graphs in linear time.Philip N. Klein  Shay Mozes  Christian Sommer  [bibtex]
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.Tsz Chiu Kwok  Lap Chi Lau  Yin Tat Lee  Shayan Oveis Gharan  Luca Trevisan  [bibtex]
Constraint satisfaction, packet routing, and the lovasz local lemma.David G. Harris  Aravind Srinivasan  [bibtex]
Sparsest cut on bounded treewidth graphs: algorithms and hardness results.Anupam Gupta  Kunal Talwar  David Witmer  [bibtex]
Fast routing table construction using small messages: extended abstract.Christoph Lenzen  Boaz Patt-Shamir  [bibtex]
Interactive proofs of proximity: delegating computation in sublinear time.Guy N. Rothblum  Salil P. Vadhan  Avi Wigderson  [bibtex]
Superlinear advantage for exact quantum algorithms.Andris Ambainis  [bibtex]
The approximate rank of a matrix and its algorithmic applications: approximate rank.Noga Alon  Troy Lee  Adi Shraibman  Santosh Vempala  [bibtex]
Shielding circuits with groups.Eric Miles  Emanuele Viola  [bibtex]
Quantum de finetti theorems under local measurements with applications.Fernando G. S. L. Brandão  Aram Wettroth Harrow  [bibtex]
Quasi-polynomial hitting-set for set-depth-Δ formulas.Manindra Agrawal  Chandan Saha  Nitin Saxena  [bibtex]
Prior-independent mechanisms for scheduling.Shuchi Chawla  Jason D. Hartline  David L. Malec  Balasubramanian Sivan  [bibtex]
Net and prune: a linear time algorithm for euclidean distance problems.Sariel Har-Peled  Benjamin Adam Raichel  [bibtex]
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.Jonathan A. Kelner  Lorenzo Orecchia  Aaron Sidford  Zeyuan Allen Zhu  [bibtex]
Extending continuous maps: polynomiality and undecidability.Martin Cadek  Marek Krcál  Jirí Matousek  Lukás Vokrínek  Uli Wagner  [bibtex]
Attribute-based encryption for circuits.Sergey Gorbunov  Vinod Vaikuntanathan  Hoeteck Wee  [bibtex]
A new approach to computing maximum flows using electrical flows.Yin Tat Lee  Satish Rao  Nikhil Srivastava  [bibtex]
Sparsity lower bounds for dimensionality reducing maps.Jelani Nelson  Huy L. Nguyên  [bibtex]
Random lattice triangulations: structure and algorithms.Pietro Caputo  Fabio Martinelli  Alistair Sinclair  Alexandre Stauffer  [bibtex]
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs.David Eisenstat  Philip N. Klein  [bibtex]
Homomorphic fingerprints under misalignments: sketching edit and shift distances.Alexandr Andoni  Assaf Goldberger  Andrew McGregor  Ely Porat  [bibtex]
Approximation resistance on satisfiable instances for predicates with few accepting inputs.Sangxia Huang  [bibtex]
Multidimensional approximate agreement in Byzantine asynchronous systems.Hammurabi Mendes  Maurice Herlihy  [bibtex]
Natural proofs versus derandomization.Ryan Williams  [bibtex]
Large-treewidth graph decompositions and applications.Chandra Chekuri  Julia Chuzhoy  [bibtex]
A PRG for lipschitz functions of polynomials with applications to sparsest cut.Daniel M. Kane  Raghu Meka  [bibtex]