| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Vincent Cohen-Addad, Anupam Gupta 0001, Philip N. Klein, Jason Li 0006 |
A quasipolynomial (2 + ε)-approximation for planar sparsest cut.  |
STOC  |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
Outcome indistinguishability. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Hazla, Alex Samorodnitsky, Ori Sberlo |
On codes decoding a constant fraction of errors on the BSC. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Aayush Jain, Huijia Lin, Amit Sahai |
Indistinguishability obfuscation from well-founded assumptions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Vishvajeet N |
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Krzysztof Nowicki 0002 |
A deterministic algorithm for the MST problem in constant rounds of congested clique. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Ran J. Tessler |
New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√n logk n) distance. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Isaac H. Kim, Eugene Tang, John Preskill |
The ghost in the radiation: robust encodings of the black hole interior (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar 0001, Madhu Sudan 0001 |
Decoding multivariate multiplicity codes on product sets. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam |
Pseudodeterministic algorithms and the structure of probabilistic time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yakov Nekrich |
Dynamic planar point location in optimal time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang |
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mina Dalirrooyfard, Nicole Wein |
Tight conditional lower bounds for approximating diameter in directed graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros |
Learning Ising models from one or multiple samples. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Radu Curticapean |
A full complexity dichotomy for immanant families. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong |
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn |
A new coreset framework for clustering. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jesper Nederlof, Karol Wegrzycki |
Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Qinxuan Pan |
Sample-optimal and efficient learning of tree Ising models. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | George Giakkoupis, Mehrdad Jafari Giv, Philipp Woelfel |
Efficient randomized DCAS. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff |
A theory of universal learning. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk 0001 |
Vertex deletion parameterized by elimination distance and even less. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell |
Fiber bundle codes: breaking the n1/2 polylog(n) barrier for Quantum LDPC codes. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyu Guo 0001, Noga Ron-Zewi |
Efficient list-decoding with constant alphabet and list sizes. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joan Bruna, Oded Regev 0001, Min Jae Song, Yi Tang |
Continuous LWE. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara |
Average-case hardness of NP from exponential worst-case hardness assumptions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani |
The complexity of gradient descent: CLS = PPAD ∩ PLS. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alfred V. Aho |
Computational thinking in programming language and compiler design (keynote). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Xin Lyu 0002 |
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nathan Keller, Ohad Klein |
Local concentration inequalities and Tomaszewski's conjecture. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Roy Schwartz 0002, Nitzan Tur |
The metric relaxation for 0-extension admits an Ω(log2/3k) gap. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zongchen Chen, Kuikui Liu, Eric Vigoda |
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay |
Lower bounds for monotone arithmetic circuits via communication complexity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco Bressan 0002 |
Efficient and near-optimal algorithms for sampling connected subgraphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai |
Breaking the quadratic barrier for matroid intersection. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic |
Tree embeddings for hop-constrained network design. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi 0001, Rebecca Reiffenhäuser |
Efficient two-sided markets with limited information. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomasz Kociumaka, Saeed Seddighin |
Improved dynamic algorithms for longest increasing subsequence. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Bill Fefferman, Zachary Remscrim |
Eliminating intermediate measurements in space-bounded Quantum computation. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Suprovat Ghoshal, Rishi Saket |
Hardness of learning DNFs using halfspaces. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
A (slightly) improved approximation algorithm for metric TSP. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Theo McKenzie, Peter Michael Reichstein Rasmussen, Nikhil Srivastava |
Support of closed walks and second eigenvalue multiplicity of graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman |
XOR lemmas for resilient functions against polynomials. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie |
Contention resolution without collision detection. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre-Étienne Meunier, Damien Regnault, Damien Woods |
The program-size complexity of self-assembled paths. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sagnik Mukhopadhyay, Danupon Nanongkai |
Weighted min-cut: sequential, cut-query, and streaming algorithms. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Aram W. Harrow, Saeed Mehraban, Mehdi Soleimanifar |
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg |
Separating the communication complexity of truthful and non-truthful combinatorial auctions. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Weiming Feng 0001, Heng Guo 0001, Yitong Yin, Chihao Zhang 0001 |
Fast sampling and counting k-SAT solutions in the local lemma regime. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li 0006 |
Extractors for adversarial sources via extremal hypergraphs. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Srikanth Srinivasan 0001 |
A robust version of Hegedus's lemma, with applications. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang 0002 |
Smoothed complexity of local max-cut and binary max-CSP. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Petra Berenbrink, George Giakkoupis, Peter Kling |
Optimal time and space leader election in population protocols. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006 |
Faster parallel algorithm for approximate shortest path. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford |
Constant girth approximation for directed graphs in subquadratic time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
Strong self-concordance and sampling. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitriy Zhuk, Barnaby Martin |
QCSP monsters and the demise of the chen conjecture. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Amos, Marios Georgiou 0001, Aggelos Kiayias, Mark Zhandry |
One-shot signatures and applications to hybrid quantum/classical authentication. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Timothy M. Chan, Shay Golan 0001, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat |
Approximating text-to-pattern Hamming distances. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Arun Jambulapati, Yin Tat Lee, Jerry Li 0001, Swati Padmanabhan, Kevin Tian |
Positive semidefinite programming: mixed, parallel, and width-independent. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Vera Traub, Jens Vygen, Rico Zenklusen |
Reducing path TSP to TSP. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Grier, Luke Schaeffer |
Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Filmus, Noam Lifshitz, Dor Minzer, Elchanan Mossel |
AND testing and robust judgement aggregation. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lap Chi Lau, Hong Zhou 0001 |
A spectral approach to network design. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lingxiao Huang, Nisheeth K. Vishnoi |
Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006 |
The Karger-Stein algorithm is optimal for k-cut. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Chong Shangguan, Itzhak Tamo |
Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Omri Shmueli |
Post-quantum zero knowledge in constant rounds. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Cristobal Rojas, Michael Yampolsky |
How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhiyi Huang 0002, Qiankun Zhang |
Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi |
Automating cutting planes is NP-hard. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhihao Jiang, Kamesh Munagala, Kangning Wang |
Approximately stable committee selection. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 0001, Meirav Zehavi |
Hitting topological minors is FPT. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song 0002 |
Solving tall dense linear programs in nearly linear time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
An improved approximation algorithm for TSP in the half integral case. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi |
Stochastic matching with few queries: (1-ε) approximation. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jesper Nederlof |
Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Alweiss, Shachar Lovett, Kewen Wu 0001, Jiapeng Zhang |
Improved bounds for the sunflower lemma. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou |
Non-adaptive adaptive sampling on turnstile streams. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Andrii Riazanov, Min Ye 0005 |
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Mitzenmacher, Saeed Seddighin |
Dynamic algorithms for LIS and distance to monotonicity. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | George Christodoulou 0001, Elias Koutsoupias, Annamária Kovács |
On the Nisan-Ronen conjecture for submodular valuations. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Vera Traub, Jens Vygen |
An improved approximation algorithm for ATSP. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis |
Quadratic speedup for finding marked vertices by quantum walks. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhihao Gavin Tang, Xiaowei Wu 0001, Yuhao Zhang 0001 |
Towards a better understanding of randomized greedy matching. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez |
Unbounded lower bound for k-server against weak adversaries. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
Walking randomly, massively, and efficiently. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Vasileios Nakos |
Top-k-convolution and the quest for near-linear output-sensitive subset sum. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | David Wajc |
Rounding dynamic matchings against an adaptive adversary. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni |
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter |
Better secret sharing via robust conditional disclosure of secrets. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang P. Liu, Aaron Sidford |
Faster energy maximization for faster maximum flow. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman, Tomer Koren, Kunal Talwar |
Private stochastic convex optimization: optimal rates in linear time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen, Jerry Li 0001, Zhao Song 0002 |
Learning mixtures of linear regressions in subexponential time via Fourier moments. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Ikenmeyer, Umangathan Kandasamy |
Implementing geometric complexity theory: on the separation of orbit closures via symmetries. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nairen Cao, Jeremy T. Fineman, Katina Russell |
Efficient construction of directed hopsets and parallel approximate shortest paths. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Carl A. Miller |
The impossibility of efficient quantum weak coin flipping. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Mingmou Liu, Huacheng Yu |
Lower bound for succinct range minimum query. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Siddharth Bhandari, Sayantan Chakraborty 0002 |
Improved bounds for perfect sampling of k-colorings in graphs. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license