default search action
46th STOC 2014: New York, NY, USA
- David B. Shmoys:
Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. ACM 2014, ISBN 978-1-4503-2710-7 - Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting codes and the price of approximate differential privacy. 1-10 - Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang:
Analyze gauss: optimal bounds for privacy-preserving principal component analysis. 11-20 - Justin Hsu
, Zhiyi Huang, Aaron Roth
Private matchings and allocations. 21-30 - Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding sum-of-squares relaxations. 31-40 - Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Constant factor approximation for balanced cut in the PIE model. 41-49 - Mohit Singh, Nisheeth K. Vishnoi:
Entropy, optimization and counting. 50-59 - Chandra Chekuri, Julia Chuzhoy:
Polynomial bounds for the grid-minor theorem. 60-69 - Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer:
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. 70-78 - Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar:
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. 79-88 - Martin Grohe
Deciding first-order properties of nowhere dense graphs. 89-98 - Sergei Artemenko, Ronen Shaltiel:
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. 99-108 - Oded Goldreich
On derandomizing algorithms that err extremely rarely. 109-118 - Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. 119-127 - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower bounds for depth 4 formulas computing iterated matrix multiplication. 128-135 - Mrinal Kumar, Shubhangi Saraf:
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in. 136-145 - Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
A super-polynomial lower bound for regular arithmetic formulas. 146-153 - Yuichi Yoshida:
A characterization of locally testable affine-invariant properties via decomposition theorems. 154-163 - Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lp-testing. 164-173 - Yi Li
Turnstile streaming algorithms might as well be linear sketches. 174-183 - Djamal Belazzougui:
Linear time construction of compressed text indices in compact space. 148-193 - Ryan Williams
New algorithms and lower bounds for circuits with linear threshold gates. 194-202 - Benjamin Rossman:
Formulas vs. circuits for small distance connectivity. 203-212 - Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. 213-222 - Alexander A. Sherstov:
Breaking the minsky-papert barrier for constant-depth circuits. 223-232 - Shahar Dobzinski, Noam Nisan
Economic efficiency requires interaction. 233-242 - Richard Cole, Tim Roughgarden:
The sample complexity of revenue maximization. 243-252 - Ning Chen, Nick Gravin, Pinyan Lu
Optimal competitive auctions. 253-262 - Thomas Rothvoß:
The matching polytope has exponential extension complexity. 263-272 - Sergey Bravyi, Matthew B. Hastings:
Homological product codes. 273-282 - Dominic W. Berry
Exponential improvement in precision for simulating sparse Hamiltonians. 283-292 - Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song:
A quantum algorithm for computing the unit group of an arbitrary degree number field. 293-302 - Thomas Kesselheim, Klaus Radke, Andreas Tönnis
Primal beats dual on online packing LPs in the random-order model. 303-312 - Sungjin Im, Janardhan Kulkarni, Kamesh Munagala:
Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints. 313-322 - Marek Cygan
Minimum bisection is fixed parameter tractable. 323-332 - Richard Peng, Daniel A. Spielman
An efficient parallel solver for SDD linear systems. 333-342 - Michael B. Cohen
Solving SDD linear systems in nearly mlog1/2n time. 343-352 - Christos Boutsidis, David P. Woodruff:
Optimal CUR matrix decompositions. 353-362 - Shay Solomon:
From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics. 363-372 - Siu-Wing Cheng
Shortest paths on polyhedral surfaces and terrains. 373-382 - Michael Elberfeld, Ken-ichi Kawarabayashi:
Embedding and canonizing graphs of bounded genus in logspace. 383-392 - Joe Neeman:
Testing surface area with arbitrary accuracy. 393-397 - Itay Berman, Iftach Haitner, Aris Tentes:
Coin flipping of any constant bias implies one-way functions. 398-407 - Iftach Haitner, Eliad Tsfadia:
An almost-optimally fair three-party coin-flipping protocol. 408-416 - Carl A. Miller, Yaoyun Shi:
Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. 417-426 - Matthew Coudron, Henry Yuen:
Infinite randomness expansion with a constant number of devices. 427-436 - Daniel M. Kane:
The average sensitivity of an intersection of half spaces. 437-440 - Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
From average case complexity to improper learning complexity. 441-448 - Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long:
The power of localization for efficiently learning linear separators with noise. 449-458 - Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres:
Bandits with switching costs: T2/3 regret. 459-467 - Paul F. Christiano:
Online local learning via semidefinite programming. 468-474 - Amit Sahai, Brent Waters:
How to use indistinguishability obfuscation: deniable encryption, and more. 475-484 - Yael Tauman Kalai, Ran Raz
How to delegate computations: the power of no-signaling proofs. 485-494 - Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, Eran Tromer:
Circuits resilient to additive attacks with applications to secure computation. 495-504 - Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen:
On the existence of extractable one-way functions. 505-514 - Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti:
Black-box non-black-box zero knowledge. 515-524 - Jugal Garg, Ruta Mehta, Vijay V. Vazirani:
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. 525-534 - Yakov Babichenko:
Query complexity of approximate nash equilibria. 535-544 - Ruta Mehta:
Constant rank bimatrix games are PPAD-hard. 545-554 - Pankaj K. Agarwal, R. Sharathkumar:
Approximation algorithms for bipartite matching with metric and geometric costs. 555-564 - Danupon Nanongkai:
Distributed approximation algorithms for weighted shortest paths. 565-573 - Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak
Parallel algorithms for geometric graph problems. 574-583 - Navin Goyal, Santosh S. Vempala, Ying Xiao:
Fourier PCA and robust tensor decomposition. 584-593 - Aditya Bhaskara, Moses Charikar
Smoothed analysis of tensor decompositions. 594-603 - Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio
Efficient density estimation via piecewise polynomial approximation. 604-613 - Venkatesan Guruswami, Prahladh Harsha
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. 614-623 - Irit Dinur
Analytical approach to parallel repetition. 624-633 - Subhash Khot, Madhur Tulsiani, Pratik Worah
A characterization of strong approximation resistance. 634-643 - László A. Végh
A strongly polynomial algorithm for generalized flow maximization. 644-653 - Shiri Chechik:
Approximate distance oracles with constant query time. 654-663 - Ryan Williams
Faster all-pairs shortest paths via circuit complexity. 664-673 - Monika Henzinger
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. 674-683 - Michael T. Goodrich:
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. 684-693 - Laurent Massoulié:
Community detection thresholds and the weak Ramanujan property. 694-703 - Hammurabi Mendes, Christine Tasson
Distributed computability in Byzantine asynchronous systems. 704-713 - Dan Alistarh, Keren Censor-Hillel, Nir Shavit:
Are lock-free concurrent algorithms practically wait-free? 714-723 - Ankit Sharma, Jan Vondrák:
Multiway cut, pairwise realizable distributions, and descending thresholds. 724-733 - Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein:
Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing. 734-743 - Zachary Friggstad, Chaitanya Swamy:
Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. 744-753 - Alina Ene, Ali Vakilian
Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements. 754-763 - Atri Rudra, Mary Wootters:
Every list-decodable code for high noise has abundant near-optimal rate puncturings. 764-773 - Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-malleable codes from additive combinatorics. 774-783 - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Breaking the quadratic barrier for 3-LCC's over the reals. 784-793 - Mohsen Ghaffari, Bernhard Haeupler
Optimal error rates for interactive coding I: adaptivity and other settings. 794-803 - Amin Coja-Oghlan:
The asymptotic k-SAT threshold. 804-813 - Jian Ding, Allan Sly, Nike Sun:
Satisfiability threshold for random regular NAE-SAT. 814-822 - Andreas Galanis, Daniel Stefankovic
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. 823-831 - Anindya De, Rocco A. Servedio
Efficient deterministic approximate counting for low-degree polynomial threshold functions. 832-841 - Shachar Lovett
Communication is bounded by root of rank. 842-846 - Mika Göös, Toniann Pitassi:
Communication lower bounds via critical block sensitivity. 847-856 - Harry Buhrman, Richard Cleve, Michal Koucký
Computing with a full memory: catalytic space. 857-866 - Michael A. Forbes, Ramprasad Saptharishi
Hitting sets for multilinear read-once algebraic branching programs, in any order. 867-875
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-12-19 22:17 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: