ACM Symposium on Theory of Computing, STOC 2018


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

Non-malleable secret sharing

Vipul Goyal, Ashutosh Kumar

Non-malleable secret sharing

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

Constant-factor approximation for ordered k-median

Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase

Constant-factor approximation for ordered k-median

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

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes

Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes

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

Improved approximation for tree augmentation: saving by rewiring

Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen

Improved approximation for tree augmentation: saving by rewiring

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

Simulation beats richness: new data-structure lower bounds

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Simulation beats richness: new data-structure lower bounds

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

On the complexity of hazard-free circuits

Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah

On the complexity of hazard-free circuits

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

Breaking the circuit-size barrier in secret sharing

Tianren Liu, Vinod Vaikuntanathan

Breaking the circuit-size barrier in secret sharing

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

Nearly work-efficient parallel algorithm for digraph reachability

Jeremy T. Fineman

Nearly work-efficient parallel algorithm for digraph reachability

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

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

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

Towards tight approximation bounds for graph diameter and eccentricities

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

Towards tight approximation bounds for graph diameter and eccentricities

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

Bounding the menu-size of approximately optimal auctions via optimal-transport duality

Yannai A. Gonczarowski

Bounding the menu-size of approximately optimal auctions via optimal-transport duality

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

Construction of new local spectral high dimensional expanders

Tali Kaufman, Izhar Oppenheim

Construction of new local spectral high dimensional expanders

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

Composable and versatile privacy via truncated CDP

Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke

Composable and versatile privacy via truncated CDP

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

Robust moment estimation and improved clustering via sum of squares

Pravesh K. Kothari, Jacob Steinhardt, David Steurer

Robust moment estimation and improved clustering via sum of squares

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

Tight query complexity lower bounds for PCA via finite sample deformed wigner law

Max Simchowitz, Ahmed El Alaoui, Benjamin Recht

Tight query complexity lower bounds for PCA via finite sample deformed wigner law

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

Almost polynomial hardness of node-disjoint paths in grids

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

Almost polynomial hardness of node-disjoint paths in grids

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

Collusion resistant traitor tracing from learning with errors

Rishab Goyal, Venkata Koppula, Brent Waters

Collusion resistant traitor tracing from learning with errors

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

Bootstrapping variables in algebraic circuits

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Bootstrapping variables in algebraic circuits

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

Capacity upper bounds for deletion-type channels

Mahdi Cheraghchi

Capacity upper bounds for deletion-type channels

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

Improved distributed algorithms for exact shortest paths

Mohsen Ghaffari, Jason Li

Improved distributed algorithms for exact shortest paths

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

Extractor-based time-space lower bounds for learning

Sumegha Garg, Ran Raz, Avishay Tal

Extractor-based time-space lower bounds for learning

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

Synchronization strings: explicit constructions, local decoding, and applications

Bernhard Haeupler, Amirbehshad Shahrasbi

Synchronization strings: explicit constructions, local decoding, and applications

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

The Paulsen problem, continuous operator scaling, and smoothed analysis

Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran

The Paulsen problem, continuous operator scaling, and smoothed analysis

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

Fine-grained complexity for sparse graphs

Udit Agarwal, Vijaya Ramachandran

Fine-grained complexity for sparse graphs

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

Generalized matrix completion and algebraic natural proofs

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Generalized matrix completion and algebraic natural proofs

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

A constant-factor approximation algorithm for the asymmetric traveling salesman problem

Ola Svensson, Jakub Tarnawski, László A. Végh

A constant-factor approximation algorithm for the asymmetric traveling salesman problem

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

A simply exponential upper bound on the maximum number of stable matchings

Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber

A simply exponential upper bound on the maximum number of stable matchings

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

Near-optimal linear decision trees for k-SUM and related problems

Daniel M. Kane, Shachar Lovett, Shay Moran

Near-optimal linear decision trees for k-SUM and related problems

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

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

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

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

Generalization and equilibrium in generative adversarial nets (GANs) (invited talk)

Tengyu Ma

Generalization and equilibrium in generative adversarial nets (GANs) (invited talk)

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

More consequences of falsifying SETH and the orthogonal vectors conjecture

Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof

More consequences of falsifying SETH and the orthogonal vectors conjecture

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

Universal protocols for information dissemination using emergent signals

Bartlomiej Dudek, Adrian Kosowski

Universal protocols for information dissemination using emergent signals

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

At the roots of dictionary compression: string attractors

Dominik Kempa, Nicola Prezza

At the roots of dictionary compression: string attractors

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

Inapproximability of the independent set polynomial in the complex plane

Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic

Inapproximability of the independent set polynomial in the complex plane

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

Constant approximation for k-median and k-means with outliers via iterative rounding

Ravishankar Krishnaswamy, Shi Li, Sai Sandeep

Constant approximation for k-median and k-means with outliers via iterative rounding

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

Deterministic distributed edge-coloring with fewer colors

Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto

Deterministic distributed edge-coloring with fewer colors

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

Cell-probe lower bounds from online communication complexity

Josh Alman, Joshua R. Wang, Huacheng Yu

Cell-probe lower bounds from online communication complexity

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

Fast algorithms for knapsack via convolution and prediction

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, Cliff Stein

Fast algorithms for knapsack via convolution and prediction

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

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing

Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing

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

Towards a proof of the 2-to-1 games conjecture?

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

Towards a proof of the 2-to-1 games conjecture?

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

Round compression for parallel matching algorithms

Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski

Round compression for parallel matching algorithms

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

Mixture models, robustness, and sum of squares proofs

Samuel B. Hopkins, Jerry Li

Mixture models, robustness, and sum of squares proofs

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

Testing conditional independence of discrete distributions

Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Testing conditional independence of discrete distributions

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

k-server via multiscale entropic regularization

Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry

k-server via multiscale entropic regularization

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

A matrix expander Chernoff bound

Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava

A matrix expander Chernoff bound

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

Incomplete nested dissection

Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang

Incomplete nested dissection

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

Holiest minimum-cost paths and flows in surface graphs

Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren

Holiest minimum-cost paths and flows in surface graphs

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

An almost-linear time algorithm for uniform random spanning tree generation

Aaron Schild

An almost-linear time algorithm for uniform random spanning tree generation

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

Operator scaling with specified marginals

Cole Franks

Operator scaling with specified marginals

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

A friendly smoothed analysis of the simplex method

Daniel Dadush, Sophie Huiberts

A friendly smoothed analysis of the simplex method

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

Quantified derandomization of linear threshold circuits

Roei Tell

Quantified derandomization of linear threshold circuits

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

Stochastic bandits robust to adversarial corruptions

Thodoris Lykouris, Vahab S. Mirrokni, Renato Paes Leme

Stochastic bandits robust to adversarial corruptions

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

Dynamic matching in school choice: efficient seat reassignment after late cancellations (invited talk)

Irene Lo

Dynamic matching in school choice: efficient seat reassignment after late cancellations (invited talk)

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

On approximating the number of k-cliques in sublinear time

Talya Eden, Dana Ron, C. Seshadhri

On approximating the number of k-cliques in sublinear time

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

Clique is hard on average for regular resolution

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov

Clique is hard on average for regular resolution

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

Succinct delegation for low-space non-deterministic computation

Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Succinct delegation for low-space non-deterministic computation

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

Counting hypergraph colourings in the local lemma regime

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Counting hypergraph colourings in the local lemma regime

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

The adaptive complexity of maximizing a submodular function

Eric Balkanski, Yaron Singer

The adaptive complexity of maximizing a submodular function

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

Multi-collision resistance: a paradigm for keyless hash functions

Nir Bitansky, Yael Tauman Kalai, Omer Paneth

Multi-collision resistance: a paradigm for keyless hash functions

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

Learning geometric concepts with nasty noise

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Learning geometric concepts with nasty noise

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

A converse to Banach's fixed point theorem and its CLS-completeness

Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis

A converse to Banach's fixed point theorem and its CLS-completeness

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

Hardness of approximate nearest neighbor search

Aviad Rubinstein

Hardness of approximate nearest neighbor search

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

Shape of diffusion and size of monochromatic region of a two-dimensional spin system

Hamed Omidvar, Massimo Franceschetti

Shape of diffusion and size of monochromatic region of a two-dimensional spin system

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

General strong polarization

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

General strong polarization

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

Nonlinear dimension reduction via outer Bi-Lipschitz extensions

Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

Nonlinear dimension reduction via outer Bi-Lipschitz extensions

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

Sparse Kneser graphs are Hamiltonian

Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak

Sparse Kneser graphs are Hamiltonian

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

Efficient decoding of random errors for quantum expander codes

Omar Fawzi, Antoine Grospellier, Anthony Leverrier

Efficient decoding of random errors for quantum expander codes

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

Discovering the roots: uniform closure results for algebraic classes under factoring

Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Discovering the roots: uniform closure results for algebraic classes under factoring

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

(Gap/S)ETH hardness of SVP

Divesh Aggarwal, Noah Stephens-Davidowitz

(Gap/S)ETH hardness of SVP

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

List-decodable robust mean estimation and learning mixtures of spherical gaussians

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

List-decodable robust mean estimation and learning mixtures of spherical gaussians

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

A generalized Turán problem and its applications

Lior Gishboliner, Asaf Shapira

A generalized Turán problem and its applications

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

Fast fencing

Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup

Fast fencing

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

Distribution-free junta testing

Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie

Distribution-free junta testing

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

A PSPACE construction of a hitting set for the closure of small algebraic circuits

Michael A. Forbes, Amir Shpilka

A PSPACE construction of a hitting set for the closure of small algebraic circuits

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

Hitting sets with near-optimal error for read-once branching programs

Mark Braverman, Gil Cohen, Sumegha Garg

Hitting sets with near-optimal error for read-once branching programs

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

Prediction with a short memory

Vatsal Sharan, Sham Kakade, Percy Liang, Gregory Valiant

Prediction with a short memory

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

The query complexity of graph isomorphism: bypassing distribution testing lower bounds

Krzysztof Onak, Xiaorui Sun

The query complexity of graph isomorphism: bypassing distribution testing lower bounds

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

Shadow tomography of quantum states

Scott Aaronson

Shadow tomography of quantum states

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

Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation

Yin Tat Lee, Santosh S. Vempala

Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation

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

Monotone circuit lower bounds from resolution

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Monotone circuit lower bounds from resolution

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

Sum-of-squares meets nash: lower bounds for finding any equilibrium

Pravesh K. Kothari, Ruta Mehta

Sum-of-squares meets nash: lower bounds for finding any equilibrium

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

The gram-schmidt walk: a cure for the Banaszczyk blues

Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett

The gram-schmidt walk: a cure for the Banaszczyk blues

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

The art gallery problem is ∃ ℝ-complete

Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

The art gallery problem is ∃ ℝ-complete

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

An optimal distributed (Δ+1)-coloring algorithm?

Yi-Jun Chang, Wenzheng Li, Seth Pettie

An optimal distributed (Δ+1)-coloring algorithm?

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

Lifting nullstellensatz to monotone span programs over any field

Toniann Pitassi, Robert Robere

Lifting nullstellensatz to monotone span programs over any field

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

Explicit binary tree codes with polylogarithmic size alphabet

Gil Cohen, Bernhard Haeupler, Leonard J. Schulman

Explicit binary tree codes with polylogarithmic size alphabet

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

Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP

Cody Murray, R. Ryan Williams

Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP

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

Fully dynamic maximal independent set with sublinear update time

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Fully dynamic maximal independent set with sublinear update time

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

Extensor-coding

Cornelius Brand, Holger Dell, Thore Husfeldt

Extensor-coding

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

Data-dependent hashing via nonlinear spectral gaps

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Data-dependent hashing via nonlinear spectral gaps

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

Fine-grained reductions from approximate counting to decision

Holger Dell, John Lapinskas

Fine-grained reductions from approximate counting to decision

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

A tighter welfare guarantee for first-price auctions

Darrell Hoy, Samuel Taggart, Zihe Wang

A tighter welfare guarantee for first-price auctions

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

Approximating generalized network design under (dis)economies of scale with applications to energy efficiency

Yuval Emek, Shay Kutten, Ron Lavi, Yangguang Shi

Approximating generalized network design under (dis)economies of scale with applications to energy efficiency

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

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

Yin Tat Lee, Santosh S. Vempala

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

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

Online load balancing on related machines

Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo

Online load balancing on related machines

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

On the parameterized complexity of approximating dominating set

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

On the parameterized complexity of approximating dominating set

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

Metric embedding via shortest path decompositions

Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman

Metric embedding via shortest path decompositions

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

Universal points in the asymptotic spectrum of tensors

Matthias Christandl, Péter Vrana, Jeroen Zuiddam

Universal points in the asymptotic spectrum of tensors

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

Consensus halving is PPA-complete

Aris Filos-Ratsikas, Paul W. Goldberg

Consensus halving is PPA-complete

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

How to match when all vertices arrive online

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu

How to match when all vertices arrive online

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

An exponential lower bound for individualization-refinement algorithms for graph isomorphism

Daniel Neuen, Pascal Schweitzer

An exponential lower bound for individualization-refinement algorithms for graph isomorphism

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

Interactive compression to external information

Mark Braverman, Gillat Kol

Interactive compression to external information

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

Smooth heaps and a dual view of self-adjusting data structures

László Kozma, Thatchaphol Saranurak

Smooth heaps and a dual view of self-adjusting data structures

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

Interactive coding over the noisy broadcast channel

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive coding over the noisy broadcast channel

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

Capacity approaching coding for low noise interactive quantum communication

Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

Capacity approaching coding for low noise interactive quantum communication

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

New classes of distributed time complexity

Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela

New classes of distributed time complexity

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

Improved pseudorandomness for unordered branching programs through local monotonicity

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Improved pseudorandomness for unordered branching programs through local monotonicity

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

The polynomial method strikes back: tight quantum query bounds via dual polynomials

Mark Bun, Robin Kothari, Justin Thaler

The polynomial method strikes back: tight quantum query bounds via dual polynomials

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

The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential

Jesús A. De Loera, Jamie Haddock, Luis Rademacher

The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential

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

Algorithmic polynomials

Alexander A. Sherstov

Algorithmic polynomials

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

On non-optimally expanding sets in Grassmann graphs

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

On non-optimally expanding sets in Grassmann graphs

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

Tight cell probe bounds for succinct Boolean matrix-vector multiplication

Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen

Tight cell probe bounds for succinct Boolean matrix-vector multiplication

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

An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time

Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li

An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time

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