ACM Symposium on Theory of Computing, STOC 2017


Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Approximate counting, the Lovasz local lemma, and inference in graphical models

Ankur Moitra

Approximate counting, the Lovasz local lemma, and inference in graphical models

Details
Discussion Comments: 0
Verification: Author has not verified information

Approximate modularity revisited

Uriel Feige, Michal Feldman, Inbal Talgam-Cohen

Approximate modularity revisited

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Linear matroid intersection is in quasi-NC

Rohit Gurjar, Thomas Thierauf

Linear matroid intersection is in quasi-NC

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding even cycles faster via capped k-walks

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel

Finding even cycles faster via capped k-walks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs

Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Bernoulli factories and black-box reductions in mechanism design

Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, Rad Niazadeh

Bernoulli factories and black-box reductions in mechanism design

Details
Discussion Comments: 0
Verification: Authors have not verified information

Real stable polynomials and matroids: optimization and counting

Damian Straszak, Nisheeth K. Vishnoi

Real stable polynomials and matroids: optimization and counting

Details
Discussion Comments: 0
Verification: Authors have not verified information

Streaming symmetric norms via measure concentration

Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang

Streaming symmetric norms via measure concentration

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient massively parallel methods for dynamic programming

Sungjin Im, Benjamin Moseley, Xiaorui Sun

Efficient massively parallel methods for dynamic programming

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

Details
Discussion Comments: 0
Verification: Authors have not verified information

Set similarity search beyond MinHash

Tobias Christiani, Rasmus Pagh

Set similarity search beyond MinHash

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deciding parity games in quasipolynomial time

Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan

Deciding parity games in quasipolynomial time

Details
Author Comments: The links http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf and http://www.comp.nus.edu.sg/~fstephan/paritygame.ps are long versions of the paper as submitted to the Special Issue of STOC 2017. The authors reserve the right to update the papers linked in the case that further improvements of the text are made. The links http://arxiv.org/abs/1703.01296 and http://arxiv.org/abs/1702.05051 are links to two follow-up papers which obtained algorithms not only running in quasipolynomial time but also in polynomial space. While the original algorithm is not implemented, the two follow-up algorithms have been implemented.
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

William M. Hoza, Chris Umans

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding approximate local minima faster than gradient descent

Naman Agarwal, Zeyuan Allen Zhu, Brian Bullins, Elad Hazan, Tengyu Ma

Finding approximate local minima faster than gradient descent

Details
Discussion Comments: 0
Verification: Authors have not verified information

New hardness results for routing on disjoint paths

Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

New hardness results for routing on disjoint paths

Details
Discussion Comments: 0
Verification: Authors have not verified information

Uniform sampling through the Lovasz local lemma

Heng Guo, Mark Jerrum, Jingcheng Liu

Uniform sampling through the Lovasz local lemma

Details
Discussion Comments: 0
Verification: Authors have not verified information

Practical post-quantum key agreement from generic lattices (invited talk)

Valeria Nikolaenko

Practical post-quantum key agreement from generic lattices (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

A quantum linearity test for robustly verifying entanglement

Anand Natarajan, Thomas Vidick

A quantum linearity test for robustly verifying entanglement

Details
Discussion Comments: 0
Verification: Authors have not verified information

The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

Pierre-Étienne Meunier, Damien Woods

The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Synchronization strings: codes for insertions and deletions approaching the Singleton bound

Bernhard Haeupler, Amirbehshad Shahrasbi

Synchronization strings: codes for insertions and deletions approaching the Singleton bound

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fully-dynamic minimum spanning forest with improved worst-case update time

Christian Wulff-Nilsen

Fully-dynamic minimum spanning forest with improved worst-case update time

Details
Discussion Comments: 0
Verification: Author has not verified information

Addition is exponentially harder than counting for shallow monotone circuits

Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio

Addition is exponentially harder than counting for shallow monotone circuits

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithms for stable and perturbation-resilient problems

Haris Angelidakis, Konstantin Makarychev, Yury Makarychev

Algorithms for stable and perturbation-resilient problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Strongly refuting random CSPs below the spectral threshold

Prasad Raghavendra, Satish Rao, Tselil Schramm

Strongly refuting random CSPs below the spectral threshold

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithmic discrepancy beyond partial coloring

Nikhil Bansal, Shashwat Garg

Algorithmic discrepancy beyond partial coloring

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient quantum tomography II

Ryan O'Donnell, John Wright

Efficient quantum tomography II

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast convergence of learning in games (invited talk)

Vasilis Syrgkanis

Fast convergence of learning in games (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

On independent sets, 2-to-2 games, and Grassmann graphs

Subhash Khot, Dor Minzer, Muli Safra

On independent sets, 2-to-2 games, and Grassmann graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Pseudodeterministic constructions in subexponential time

Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic constructions in subexponential time

Details
Discussion Comments: 0
Verification: Authors have not verified information

The menu-size complexity of revenue approximation

Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan

The menu-size complexity of revenue approximation

Details
Discussion Comments: 0
Verification: Authors have not verified information

The next 700 network programming languages (invited talk)

Nate Foster

The next 700 network programming languages (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Subquadratic submodular function minimization

Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

Subquadratic submodular function minimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Geodesic walks in polytopes

Yin Tat Lee, Santosh Srinivas Vempala

Geodesic walks in polytopes

Details
Discussion Comments: 0
Verification: Authors have not verified information

A strongly polynomial algorithm for bimodular integer linear programming

Stephan Artmann, Robert Weismantel, Rico Zenklusen

A strongly polynomial algorithm for bimodular integer linear programming

Details
Discussion Comments: 0
Verification: Authors have not verified information

Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

Communication complexity of approximate Nash equilibria

Details
Discussion Comments: 0
Verification: Authors have not verified information

The limitations of optimization from samples

Eric Balkanski, Aviad Rubinstein, Yaron Singer

The limitations of optimization from samples

Details
Discussion Comments: 0
Verification: Authors have not verified information

Katyusha: the first direct acceleration of stochastic gradient methods

Zeyuan Allen Zhu

Katyusha: the first direct acceleration of stochastic gradient methods

Details
Discussion Comments: 0
Verification: Author has not verified information

A generalization of permanent inequalities and applications in counting and optimization

Nima Anari, Shayan Oveis Gharan

A generalization of permanent inequalities and applications in counting and optimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sum of squares lower bounds for refuting any CSP

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer

Sum of squares lower bounds for refuting any CSP

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local max-cut in smoothed polynomial time

Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei

Local max-cut in smoothed polynomial time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Non-malleable codes and extractors for small-depth circuits, and affine functions

Eshan Chattopadhyay, Xin Li

Non-malleable codes and extractors for small-depth circuits, and affine functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal mean-based algorithms for trace reconstruction

Anindya De, Ryan O'Donnell, Rocco A. Servedio

Optimal mean-based algorithms for trace reconstruction

Details
Discussion Comments: 0
Verification: Authors have not verified information

Probabilistic rank and matrix rigidity

Josh Alman, R. Ryan Williams

Probabilistic rank and matrix rigidity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lossy kernelization

Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh

Lossy kernelization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Beating 1-1/e for ordered prophets

Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, Brendan Lucier

Beating 1-1/e for ordered prophets

Details
Discussion Comments: 0
Verification: Authors have not verified information

Why prices need algorithms (invited talk)

Tim Roughgarden, Inbal Talgam-Cohen

Why prices need algorithms (invited talk)

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Sampling random spanning trees faster than matrix multiplication

David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva

Sampling random spanning trees faster than matrix multiplication

Details
Discussion Comments: 0
Verification: Authors have not verified information

A reverse Minkowski theorem

Oded Regev, Noah Stephens-Davidowitz

A reverse Minkowski theorem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Xi Chen, Erik Waingarten, Jinyu Xie

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the complexity of local distributed graph problems

Mohsen Ghaffari, Fabian Kuhn, Yannic Maus

On the complexity of local distributed graph problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Average-case fine-grained hardness

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

Average-case fine-grained hardness

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Hardness amplification for entangled games via anchoring

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Hardness amplification for entangled games via anchoring

Details
Discussion Comments: 0
Verification: Authors have not verified information

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

Fabrizio Grandoni, Bundit Laekhanukit

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

Details
Discussion Comments: 0
Verification: Authors have not verified information

Homomorphisms are a good basis for counting small subgraphs

Radu Curticapean, Holger Dell, Dániel Marx

Homomorphisms are a good basis for counting small subgraphs

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Low rank approximation with entrywise l1-norm error

Zhao Song, David P. Woodruff, Peilin Zhong

Low rank approximation with entrywise l1-norm error

Details
Discussion Comments: 0
Verification: Authors have not verified information

Towards optimal two-source extractors and Ramsey graphs

Gil Cohen

Towards optimal two-source extractors and Ramsey graphs

Details
Discussion Comments: 0
Verification: Author has not verified information

Removal lemmas with polynomial bounds

Lior Gishboliner, Asaf Shapira

Removal lemmas with polynomial bounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient empirical revenue maximization in single-parameter auction environments

Yannai A. Gonczarowski, Noam Nisan

Efficient empirical revenue maximization in single-parameter auction environments

Details
Discussion Comments: 0
Verification: Authors have not verified information

Quantum entanglement, sum of squares, and the log rank conjecture

Boaz Barak, Pravesh K. Kothari, David Steurer

Quantum entanglement, sum of squares, and the log rank conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Learning from untrusted data

Moses Charikar, Jacob Steinhardt, Gregory Valiant

Learning from untrusted data

Details
Discussion Comments: 0
Verification: Authors have not verified information

Provable learning of noisy-OR networks

Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski

Provable learning of noisy-OR networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

The computational complexity of ball permutations

Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban

The computational complexity of ball permutations

Details
Discussion Comments: 0
Verification: Authors have not verified information

Stability of service under time-of-use pricing

Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, Balasubramanian Sivan

Stability of service under time-of-use pricing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

Danupon Nanongkai, Thatchaphol Saranurak

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed exact shortest paths in sublinear time

Michael Elkin

Distributed exact shortest paths in sublinear time

Details
Discussion Comments: 0
Verification: Author has not verified information

Complexity of short Presburger arithmetic

Danny Nguyen, Igor Pak

Complexity of short Presburger arithmetic

Details
Discussion Comments: 0
Verification: Authors have not verified information

A weighted linear matroid parity algorithm

Satoru Iwata, Yusuke Kobayashi

A weighted linear matroid parity algorithm

Details
Discussion Comments: 0
Verification: Authors have not verified information

Twenty (simple) questions

Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran

Twenty (simple) questions

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Optimizing tree pattern queries: why cutting is not enough (invited talk)

Wim Martens

Optimizing tree pattern queries: why cutting is not enough (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Kolmogorov complexity version of Slepian-Wolf coding

Marius Zimand

Kolmogorov complexity version of Slepian-Wolf coding

Details
Discussion Comments: 0
Verification: Author has not verified information

Information-theoretic thresholds from the cavity method

Amin Coja-Oghlan, Florent Krzakala, Will Perkins, Lenka Zdeborová

Information-theoretic thresholds from the cavity method

Details
Discussion Comments: 0
Verification: Authors have not verified information

Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk)

Atri Rudra

Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Strongly exponential lower bounds for monotone computation

Toniann Pitassi, Robert Robere

Strongly exponential lower bounds for monotone computation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online and dynamic algorithms for set cover

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi

Online and dynamic algorithms for set cover

Details
Discussion Comments: 0
Verification: Authors have not verified information

A time- and message-optimal distributed algorithm for minimum spanning trees

Gopal Pandurangan, Peter Robinson, Michele Scquizzato

A time- and message-optimal distributed algorithm for minimum spanning trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized polynomial time identity testing for noncommutative circuits

Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja

Randomized polynomial time identity testing for noncommutative circuits

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximate near neighbors for general symmetric norms

Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Approximate near neighbors for general symmetric norms

Details
Discussion Comments: 0
Verification: Authors have not verified information

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy

Details
Discussion Comments: 0
Verification: Authors have not verified information

Area-convexity, l regularization, and undirected multicommodity flow

Jonah Sherman

Area-convexity, l regularization, and undirected multicommodity flow

Details
Discussion Comments: 0
Verification: Author has not verified information

Compression of quantum multi-prover interactive proofs

Zhengfeng Ji

Compression of quantum multi-prover interactive proofs

Details
Discussion Comments: 0
Verification: Author has not verified information

Pseudorandomness of ring-LWE for any ring and modulus

Chris Peikert, Oded Regev, Noah Stephens-Davidowitz

Pseudorandomness of ring-LWE for any ring and modulus

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Recent trends in decentralized cryptocurrencies (invited talk)

Aviv Zohar

Recent trends in decentralized cryptocurrencies (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Decremental single-source reachability in planar digraphs

Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Piotr Sankowski

Decremental single-source reachability in planar digraphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online service with delay

Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi

Online service with delay

Details
Discussion Comments: 0
Verification: Authors have not verified information

Trace reconstruction with exp(O(n1/3)) samples

Fedor Nazarov, Yuval Peres

Trace reconstruction with exp(O(n1/3)) samples

Details
Discussion Comments: 0
Verification: Authors have not verified information

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

Assaf Naor, Robert Young

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

Details
Discussion Comments: 0
Verification: Authors have not verified information

Kernel-based methods for bandit convex optimization

Sébastien Bubeck, Yin Tat Lee, Ronen Eldan

Kernel-based methods for bandit convex optimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exponential separation of quantum communication and classical information

Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu

Exponential separation of quantum communication and classical information

Details
Discussion Comments: 0
Verification: Authors have not verified information

Formula lower bounds via the quantum method

Avishay Tal

Formula lower bounds via the quantum method

Details
Discussion Comments: 0
Verification: Author has not verified information

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exponential separations in the energy complexity of leader election

Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan

Exponential separations in the energy complexity of leader election

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster space-efficient algorithms for subset sum and k-sum

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

Faster space-efficient algorithms for subset sum and k-sum

Details
Discussion Comments: 0
Verification: Authors have not verified information

Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

Jin-Yi Cai, Zhiguo Fu

Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

Details
Discussion Comments: 0
Verification: Authors have not verified information

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

Orna Kupferman

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Explicit, almost optimal, epsilon-balanced codes

Amnon Ta-Shma

Explicit, almost optimal, epsilon-balanced codes

Details
Discussion Comments: 0
Verification: Author has not verified information

Non-interactive delegation and batch NP verification from standard computational assumptions

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Non-interactive delegation and batch NP verification from standard computational assumptions

Details
Discussion Comments: 0
Verification: Authors have not verified information

DecreaseKeys are expensive for external memory priority queues

Kasper Eenberg, Kasper Green Larsen, Huacheng Yu

DecreaseKeys are expensive for external memory priority queues

Details
Discussion Comments: 0
Verification: Authors have not verified information

Time-space hardness of learning sparse parities

Gillat Kol, Ran Raz, Avishay Tal

Time-space hardness of learning sparse parities

Details
Discussion Comments: 0
Verification: Authors have not verified information

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

Pasin Manurangsi

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

Details
Discussion Comments: 0
Verification: Author has not verified information

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

Andris Ambainis, Martins Kokainis

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

Details
Discussion Comments: 0
Verification: Authors have not verified information

Simple mechanisms for subadditive buyers via duality

Yang Cai, Mingfei Zhao

Simple mechanisms for subadditive buyers via duality

Details
Discussion Comments: 0
Verification: Authors have not verified information

An adaptive sublinear-time block sparse fourier transform

Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh

An adaptive sublinear-time block sparse fourier transform

Details
Discussion Comments: 0
Verification: Authors have not verified information

An SDP-based algorithm for linear-sized spectral sparsification

Yin Tat Lee, He Sun

An SDP-based algorithm for linear-sized spectral sparsification

Details
Discussion Comments: 0
Verification: Authors have not verified information

A simpler and faster strongly polynomial algorithm for generalized flow maximization

Neil Olver, László A. Végh

A simpler and faster strongly polynomial algorithm for generalized flow maximization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved non-malleable extractors, non-malleable codes and independent source extractors

Xin Li

Improved non-malleable extractors, non-malleable codes and independent source extractors

Details
Discussion Comments: 0
Verification: Author has not verified information

A polynomial restriction lemma with applications

Valentine Kabanets, Daniel M. Kane, Zhenjian Lu

A polynomial restriction lemma with applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

How well do local algorithms solve semidefinite programs?

Zhou Fan, Andrea Montanari

How well do local algorithms solve semidefinite programs?

Details
Discussion Comments: 0
Verification: Authors have not verified information