| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Guang Hao Low |
Hamiltonian simulation with nearly optimal dependence on spectral norm.  |
STOC  |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dylan M. McKay, Cody D. Murray, R. Ryan Williams |
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006, Merav Parter |
Planar diameter via metric compression. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Potechin |
On the approximation resistance of balanced linear threshold functions. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alina Ene, Huy L. Nguyen, Adrian Vladu |
Submodular maximization with matroid and packing constraints in parallel. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sandip Sinha, Omri Weinstein |
Local decodability of the Burrows-Wheeler transform. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran |
Private PAC learning implies finite Littlestone dimension. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Yu Chen 0039, Sanjeev Khanna |
Polynomial pass lower bounds for graph streaming algorithms. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Costin Badescu, Ryan O'Donnell, John Wright 0004 |
Quantum state certification. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, Chaitanya Swamy |
Approximation algorithms for minimum norm and ordered optimization problems. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sebastian Forster, Gramoz Goranci |
Dynamic low-stretch trees via dynamic low-diameter decompositions. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif |
The log-approximate-rank conjecture is false. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh |
A universal sampling method for reconstructing signals with simple Fourier transforms. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Kent Quanrud |
Parallelizing greedy for submodular set function maximization in matroids and beyond. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Martin Farach-Colton, William Kuszmaul |
Achieving optimal backlog in multi-processor cup games. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin |
1+ε approximation of tree edit distance in quadratic time. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Hedyeh Beyhaghi, S. Matthew Weinberg |
Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vasileios Nakos, Zhao Song 0002 |
Stronger l2/l2 compressed sensing; without iterating. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Kun He 0011, Qian Li 0012, Xiaoming Sun 0001, Jiapeng Zhang |
Quantum Lovász local lemma: Shearer's bound is tight. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Omar Alrabiah, Venkatesan Guruswami |
An exponential lower bound on the sub-packetization of MSR codes. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dominik Kempa, Tomasz Kociumaka |
String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Arun Ganesh, Qiuyi (Richard) Zhang |
Optimal sequence length requirements for phylogenetic tree reconstruction with indels. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mina Dalirrooyfard, Thuy-Duong Vuong, Virginia Vassilevska Williams |
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov, Pei Wu |
Near-optimal lower bounds on the threshold degree and sign-rank of AC0. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | André Linhares, Chaitanya Swamy |
Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Alexander Golovnev, Omri Weinstein |
Static data structure lower bounds imply rigidity. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Holmgren, Lisa Yang 0001 |
The parallel repetition of non-signaling games: counterexamples and dichotomy. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Guy N. Rothblum |
Gentle measurement of quantum states and differential privacy. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aris Filos-Ratsikas, Paul W. Goldberg |
The complexity of splitting necklaces and bisecting ham sandwiches. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka |
Sylvester-Gallai type theorems for quadratic polynomials. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami |
CSPs with global modular constraints: algorithms and hardness via polynomial representations. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jingcheng Liu 0001, Kunal Talwar |
Private selection from private candidates. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi |
Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen |
Quantum proof systems for iterated exponential time, and beyond. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
Polylogarithmic approximation for Euler genus on bounded degree graphs. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Huacheng Yu |
Optimal succinct rank data structure via approximate nonnegative tensor decomposition. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Coester, Elias Koutsoupias |
The online k-taxi problem. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Wojciech Czerwinski, Slawomir Lasota 0001, Ranko Lazic 0001, Jérôme Leroux, Filip Mazowiecki |
The reachability problem for Petri nets is not elementary. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabrizio Grandoni 0001, Bundit Laekhanukit, Shi Li 0001 |
O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan 0001, Utkarsh Tripathi, S. Venkitesh |
A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | David Durfee, Yu Gao 0001, Gramoz Goranci, Richard Peng |
Fully dynamic spectral vertex sparsifiers and applications. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Tauman Kalai, Omer Paneth, Lisa Yang 0001 |
How to delegate computations publicly. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Dakshita Khurana, Omer Paneth |
Weak zero-knowledge beyond the black-box barrier. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brakensiek, Venkatesan Guruswami |
Bridging between 0/1 and linear programming via random walks. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Marvin Künnemann, Karol Wegrzycki |
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jugal Garg, László A. Végh |
A strongly polynomial algorithm for linear exchange markets. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishesh Jain, Frederic Koehler, Andrej Risteski |
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Navin Goyal, Abhishek Shetty |
Non-Gaussian component analysis using entropy methods. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001 |
On a generalization of iterated and randomized rounding. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Bresler, Frederic Koehler, Ankur Moitra |
Learning restricted Boltzmann machines via influence maximization. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Erik Waingarten |
Testing unateness nearly optimally. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Roei Tell |
Bootstrapping results for threshold circuits "just beyond" known lower bounds. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen |
Decremental strongly-connected components and single-source reachability in near-linear time. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu |
Why extension-based proofs fail. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessio Conte, Takeaki Uno |
New polynomial delay bounds for maximal subgraph enumeration by proximity search. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
Fooling polytopes. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum |
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Yin Tat Lee, Zhao Song 0002 |
Solving linear programs in the current matrix multiplication time. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Avishay Tal |
Oracle separation of BQP and PH. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jian Ding, Nike Sun |
Capacity lower bound for the Ising perceptron. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Dmitry Krachun |
An optimal space lower bound for approximating MAX-CUT. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Canetti, Yilei Chen 0001, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs |
Fiat-Shamir: from practice to theory. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ewin Tang |
A quantum-inspired classical algorithm for recommendation systems. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Tyler Helmuth, Will Perkins 0001, Guus Regts |
Algorithmic Pirogov-Sinai theory. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Danupon Nanongkai |
Distributed exact weighted all-pairs shortest paths in near-linear time. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaonan Jin, Pinyan Lu, Qi Qi 0003, Zhihao Gavin Tang, Tao Xiao |
Tight approximation ratio of anonymous pricing. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke |
Competitively chasing convex bodies. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang 0005 |
Flows in almost linear time via adaptive preconditioning. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Atul Singh Arora, Jérémie Roland, Stephan Weis |
Quantum weak coin flipping. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Balkanski, Yaron Singer |
The adaptive complexity of maximizing a submodular function. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant |
Prediction with a short memory. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela |
New classes of distributed time complexity. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Omar Fawzi, Antoine Grospellier, Anthony Leverrier |
Efficient decoding of random errors for quantum expander codes. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal |
Improved pseudorandomness for unordered branching programs through local monotonicity. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Algorithmic polynomials. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak |
Sparse Kneser graphs are Hamiltonian. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden |
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Mahdi Cheraghchi |
Capacity upper bounds for deletion-type channels. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Krzysztof Onak, Xiaorui Sun |
The query complexity of graph isomorphism: bypassing distribution testing lower bounds. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra |
On non-optimally expanding sets in Grassmann graphs. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Ashutosh Kumar 0002 |
Non-malleable secret sharing. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Yael Tauman Kalai, Omer Paneth |
Multi-collision resistance: a paradigm for keyless hash functions. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Schild |
An almost-linear time algorithm for uniform random spanning tree generation. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Heng Guo 0001, Chao Liao, Pinyan Lu, Chihao Zhang 0001 |
Counting hypergraph colourings in the local lemma regime. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Jesús A. De Loera, Jamie Haddock, Luis Rademacher |
The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan 0001 |
General strong polarization. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Sumanta Ghosh, Nitin Saxena 0001 |
Bootstrapping variables in algebraic circuits. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Yin Tat Lee, Santosh S. Vempala |
Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Forbes 0001, Amir Shpilka |
A PSPACE construction of a hitting set for the closure of small algebraic circuits. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabrizio Grandoni 0001, Tobias Mömke, Andreas Wiese, Hang Zhou 0001 |
A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Garg, Yin Tat Lee, Zhao Song 0002, Nikhil Srivastava |
A matrix expander Chernoff bound. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Darrell Hoy, Samuel Taggart, Zihe Wang 0001 |
A tighter welfare guarantee for first-price auctions. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Cody Murray, R. Ryan Williams |
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
Nonlinear dimension reduction via outer Bi-Lipschitz extensions. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Pravesh K. Kothari, Jacob Steinhardt, David Steurer |
Robust moment estimation and improved clustering via sum of squares. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Gil Cohen, Sumegha Garg |
Hitting sets with near-optimal error for read-once branching programs. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Bartlomiej Dudek 0001, Adrian Kosowski |
Universal protocols for information dissemination using emergent signals. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Sumegha Garg, Ran Raz, Avishay Tal |
Extractor-based time-space lower bounds for learning. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license