default search action
45th STOC 2013: Palo Alto, CA, USA
- Dan Boneh, Tim Roughgarden, Joan Feigenbaum:
Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013. ACM 2013, ISBN 978-1-4503-2029-0
1A
- Daniel M. Kane, Raghu Meka:
A PRG for lipschitz functions of polynomials with applications to sparsest cut. 1-10 - Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
:
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. 11-20 - Ryan Williams
Natural proofs versus derandomization. 21-30 - Xiaohui Bei
On the complexity of trial and error. 31-40
1B
- Kshipra Bhawalkar, Sreenivas Gollapudi, Kamesh Munagala
Coevolutionary opinion formation games. 41-50 - Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan:
Prior-independent mechanisms for scheduling. 51-60 - Michal Feldman, Nick Gravin, Brendan Lucier:
Combinatorial walrasian equilibrium. 61-70 - Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative grothendieck inequality. 71-80
2A
- Kenneth L. Clarkson, David P. Woodruff:
Low rank approximation and regression in input sparsity time. 81-90 - Xiangrui Meng, Michael W. Mahoney:
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. 91-100 - Jelani Nelson, Huy L. Nguyen:
Sparsity lower bounds for dimensionality reducing maps. 101-110 - Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer:
Recursive composition and bootstrapping for SNARKS and proof-carrying data. 111-120 - Moritz Hardt, David P. Woodruff:
How robust are linear sketches to adaptive inputs? 121-130
2B
- Stanislav Böhm, Stefan Göller, Petr Jancar
Equivalence of deterministic one-counter automata is NL-complete. 131-140 - Peter Bürgisser, Christian Ikenmeyer:
Explicit lower bounds via geometric complexity theory. 141-150 - Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
From information to exact communication. 151-160 - Mark Braverman, Ankur Moitra:
An information complexity approach to extended formulations. 161-170 - Ilan Komargodski, Ran Raz
Average-case lower bounds for formula size. 171-180
3A
- Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The complexity of non-monotone markets. 181-190 - Yun Kuen Cheung, Richard Cole, Nikhil R. Devanur:
Tatonnement beyond gross substitutes?: gradient descent to the rescue. 191-200 - Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier:
Simultaneous auctions are (almost) efficient. 201-210 - Vasilis Syrgkanis, Éva Tardos:
Composable and efficient mechanisms. 211-220
3B
- Vipul Goyal:
Non-black-box simulation in the fully concurrent setting. 221-230 - Kai-Min Chung, Rafael Pass
Non-black-box simulation from one-way functions and applications to resettable security. 231-240 - Nir Bitansky, Omer Paneth:
On the impossibility of approximate obfuscation and applications to resettable cryptography. 241-250 - Eric Miles, Emanuele Viola:
Shielding circuits with groups. 251-260
4A
- László Babai
Quasipolynomial-time canonical form for steiner designs. 261-270 - Xi Chen, Xiaorui Sun, Shang-Hua Teng:
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. 271-280 - Anupam Gupta, Kunal Talwar, David Witmer:
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. 281-290 - Chandra Chekuri, Julia Chuzhoy:
Large-treewidth graph decompositions and applications. 291-300 - Marek Cygan
Fast hamiltonicity checking via bases of perfect matchings. 301-310 - Peter Keevash, Fiachra Knox, Richard Mycroft:
Polynomial-time perfect matchings in dense hypergraphs. 311-320
4B
- Manindra Agrawal, Chandan Saha, Nitin Saxena
Quasi-polynomial hitting-set for set-depth-Δ formulas. 321-330 - Moritz Hardt, Aaron Roth
Beyond worst-case analysis in private singular vector computation. 331-340 - Justin Hsu
Differential privacy for the analyst via private equilibrium computation. 341-350 - Aleksandar Nikolov, Kunal Talwar, Li Zhang:
The geometry of differential privacy: the sparse and approximate cases. 351-360 - Jonathan R. Ullman:
Answering n{2+o(1)} counting queries with differential privacy is hard. 361-370
5A
- Mikkel Thorup
Bottom-k and priority sampling, set similarity and subset sums with minimal independence. 371-380 - Christoph Lenzen, Boaz Patt-Shamir:
Fast routing table construction using small messages: extended abstract. 381-390 - Hammurabi Mendes, Maurice Herlihy:
Multidimensional approximate agreement in Byzantine asynchronous systems. 391-400 - Valerie King, Jared Saia:
Byzantine agreement in polynomial expected time: [extended abstract]. 401-410
5B
- Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for boolean functions over the hypercube. 411-418 - Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. 419-428 - Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami
Every locally characterized affine-invariant property is testable. 429-436 - Ken-ichi Kawarabayashi, Yuichi Yoshida:
Testing subdivision-freeness: property testing meets structural graph theory. 437-446
6A
- Siu On Chan:
Approximation resistance from pairwise independent subgroups. 447-456 - Sangxia Huang:
Approximation resistance on satisfiable instances for predicates with few accepting inputs. 457-466 - Sanjam Garg
Witness encryption and its applications. 467-476 - Anindya De, Elchanan Mossel
Majority is stablest: discrete and SoS. 477-486 - Christopher Beck
Strong ETH holds for regular resolution. 487-494
6B
- James R. Lee, Manor Mendel, Mohammad Moharrami:
A node-capacitated okamura-seymour theorem. 495-504 - Philip N. Klein, Shay Mozes
Structured recursive separator decompositions for planar graphs in linear time. 505-514 - Liam Roditty, Virginia Vassilevska Williams:
Fast approximation algorithms for the diameter and radius of sparse graphs. 515-524 - Albert Gu, Anupam Gupta, Amit Kumar
The power of deferral: maintaining a constant-competitive steiner tree online. 525-534 - Niv Buchbinder
Simplex partitioning via exponential clocks and the multiway cut problem. 535-544
7A
- Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee:
Attribute-based encryption for circuits. 545-554 - Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich:
Reusable garbled circuits and succinct functional encryption. 555-564 - Yael Tauman Kalai, Ran Raz
Delegation for bounded space. 565-574 - Zvika Brakerski, Adeline Langlois
Classical hardness of learning with errors. 575-584 - Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer:
On the concrete efficiency of probabilistically-checkable proofs. 585-594
7B
- Martin Cadek
Extending continuous maps: polynomiality and undecidability. 595-604 - Sariel Har-Peled
Net and prune: a linear time algorithm for euclidean distance problems. 605-614 - Pietro Caputo, Fabio Martinelli
Random lattice triangulations: structure and algorithms. 615-624 - Alistair Sinclair, Piyush Srivastava:
Lee-Yang theorems and the complexity of computing averages. 625-634 - Jin-Yi Cai, Heng Guo, Tyson Williams:
A complete dichotomy rises from the capture of vanishing signatures: extended abstract. 635-644
8A
- Michael Elkin, Shay Solomon:
Optimal euclidean spanners: really short, thin and lanky. 645-654 - Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao:
Statistical algorithms and a lower bound for detecting planted cliques. 655-664 - Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi:
Low-rank matrix completion using alternating minimization. 665-674 - Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala:
The approximate rank of a matrix and its algorithmic applications: approximate rank. 675-684
8B
- David G. Harris, Aravind Srinivasan:
Constraint satisfaction, packet routing, and the lovasz local lemma. 685-694 - Johan Thapper
The complexity of finite-valued CSPs. 695-704 - Amin Coja-Oghlan, Konstantinos Panagiotou:
Going after the k-SAT threshold. 705-714 - Gillat Kol, Ran Raz
Interactive channel capacity. 715-724
9A
- Aaron Bernstein:
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. 725-734 - David Eisenstat, Philip N. Klein:
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. 735-744 - Ofer Neiman, Shay Solomon:
Simple deterministic algorithms for fully dynamic maximal matching. 745-754 - Yin Tat Lee, Satish Rao, Nikhil Srivastava:
A new approach to computing maximum flows using electrical flows. 755-764 - James B. Orlin
Max flows in O(nm) time, or better. 765-774
9B
- Karl Bringmann, Kasper Green Larsen:
Succinct sampling from discrete distributions. 775-782 - Xin Li:
New independent source extractors with exponential improvement. 783-792 - Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson:
Interactive proofs of proximity: delegating computation in sublinear time. 793-802 - Miklós Ajtai:
Lower bounds for RAMs and quantifier elimination. 803-812 - Chris Beck
Some trade-off results for polynomial calculus: extended abstract. 813-822
10A
- Abhishek Bhowmick, Zeev Dvir, Shachar Lovett
New bounds for matching vector families. 823-832 - Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf:
A new family of locally correctable codes based on degree-lifted algebraic geometry codes. 833-842 - Venkatesan Guruswami, Chaoping Xing:
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. 843-852 - Mary Wootters:
On the list decodability of random linear codes with large error rates. 853-860
10B
- Fernando G. S. L. Brandão, Aram W. Harrow
Quantum de finetti theorems under local measurements with applications. 861-870 - Fernando G. S. L. Brandão, Aram W. Harrow
Product-state approximations to quantum ground states. 871-880 - Amnon Ta-Shma
Inverting well conditioned matrices in quantum logspace. 881-890 - Andris Ambainis:
Superlinear advantage for exact quantum algorithms. 891-900
11A
- Shi Li, Ola Svensson:
Approximating k-median via pseudo-approximation. 901-910 - Jonathan A. Kelner, Lorenzo Orecchia
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. 911-920 - Alexander A. Sherstov:
Communication lower bounds using directional derivatives. 921-930 - Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat:
Homomorphic fingerprints under misalignments: sketching edit and shift distances. 931-940
11B
- Ventsislav Chonev, Joël Ouaknine
The orbit problem in higher dimensions. 941-950 - Yossi Azar, Ilan Reuven Cohen, Iftah Gamzu:
The loss of serving in the dark. 951-960 - Yossi Azar, Ilan Reuven Cohen, Seny Kamara, F. Bruce Shepherd:
Tight bounds for online vector bin packing. 961-970 - Jian Li, Wen Yuan:
Stochastic combinatorial optimization via poisson approximation. 971-980
Knuth-prize lecture
- Gary L. Miller:
Solving large optimization problems using spectral graph theory. 981
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-26 20:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: