| 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 Mendes de 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
|
|
Pierre-Étienne Meunier, Damien Woods |
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
|
|
Yin Tat Lee, Santosh S. Vempala |
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
|
|
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh |
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
|
|
Oded Regev, Noah Stephens-Davidowitz |
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
|
|
Fabrizio Grandoni, Bundit Laekhanukit |
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
|
|
Moses Charikar, Jacob Steinhardt, Gregory Valiant |
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
|
|
Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran |
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
|
|
Atri Rudra |
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
|
|
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma |
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
|
|
Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi |
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
|
|
Assaf Naor, Robert Young |
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
|
|
Orna Kupferman |
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
|