ACM Symposium on Discrete Algorithms, SODA 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

Maximally Recoverable Codes for Grid-like Topologies

Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

Maximally Recoverable Codes for Grid-like Topologies

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

Connectivity Oracles for Graphs Subject to Vertex Failures

Ran Duan, Seth Pettie

Connectivity Oracles for Graphs Subject to Vertex Failures

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

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

David Adjiashvili

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

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

Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

Lucas Boczkowski, Amos Korman, Emanuele Natale

Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

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

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems

Chandra Chekuri, Kent Quanrud

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems

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

A Faster Pseudopolynomial Time Algorithm for Subset Sum

Konstantinos Koiliaris, Chao Xu

A Faster Pseudopolynomial Time Algorithm for Subset Sum

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

Competitive analysis of the top-K ranking problem

Xi Chen, Sivakanth Gopi, Jieming Mao, Jon Schneider

Competitive analysis of the top-K ranking problem

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

Tight Bounds for Online TSP on the Line

Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, Leen Stougie

Tight Bounds for Online TSP on the Line

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

LSH Forest: Practical Algorithms Made Theoretical

Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki

LSH Forest: Practical Algorithms Made Theoretical

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

Sparse Suffix Tree Construction in Optimal Time and Space

Pawel Gawrychowski, Tomasz Kociumaka

Sparse Suffix Tree Construction in Optimal Time and Space

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

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Adrian Kosowski, Laurent Viennot

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

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

Three Colors Suffice: Conflict-Free Coloring of Planar Graphs

Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, Christian Scheffer

Three Colors Suffice: Conflict-Free Coloring of Planar Graphs

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

Probabilistic clustering of high dimensional norms

Assaf Naor

Probabilistic clustering of high dimensional norms

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

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

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

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

Sergio Cabello

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

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

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space

Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space

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

Adaptive Matrix Vector Product

Santosh Srinivas Vempala, David P. Woodruff

Adaptive Matrix Vector Product

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

Optimization of Bootstrapping in Circuits

Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, Hang Zhou

Optimization of Bootstrapping in Circuits

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

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number

Clément Maria, Jonathan Spreer

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number

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

File Maintenance: When in Doubt, Change the Layout!

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, Pablo Montes

File Maintenance: When in Doubt, Change the Layout!

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

Parameter-free Topology Inference and Sparsification for Data on Manifolds

Tamal K. Dey, Zhe Dong, Yusu Wang

Parameter-free Topology Inference and Sparsification for Data on Manifolds

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

Popularity, Mixed Matchings, and Self-duality

Chien-Chung Huang, Telikepalli Kavitha

Popularity, Mixed Matchings, and Self-duality

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

Combinatorial Prophet Inequalities

Aviad Rubinstein, Sahil Singla

Combinatorial Prophet Inequalities

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

Bridging the Capacity Gap Between Interactive and One-Way Communication

Bernhard Haeupler, Ameya Velingker

Bridging the Capacity Gap Between Interactive and One-Way Communication

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

Partial and Constrained Level Planarity

Guido Brückner, Ignaz Rutter

Partial and Constrained Level Planarity

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

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

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

Eliminating Depth Cycles among Triangles in Three Dimensions

Boris Aronov, Edward Y. Miller, Micha Sharir

Eliminating Depth Cycles among Triangles in Three Dimensions

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

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Amir Abboud, Greg Bodwin, Seth Pettie

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

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

Convergence of Incentive-Driven Dynamics in Fisher Markets

Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman

Convergence of Incentive-Driven Dynamics in Fisher Markets

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

The (h, k)-Server Problem on Bounded Depth Trees

Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos

The (h, k)-Server Problem on Bounded Depth Trees

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

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma

David G. Harris

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma

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

Firefighting on Trees Beyond Integrality Gaps

David Adjiashvili, Andrea Baggio, Rico Zenklusen

Firefighting on Trees Beyond Integrality Gaps

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

Distance Sensitive Bloom Filters Without False Negatives

Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen

Distance Sensitive Bloom Filters Without False Negatives

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

Random Walks and Evolving Sets: Faster Convergences and Limitations

Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau

Random Walks and Evolving Sets: Faster Convergences and Limitations

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

A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs

Amir Nayyeri, Benjamin Raichel

A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs

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

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

Xue Chen, Yuan Zhou

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

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

Hardness of Permutation Pattern Matching

Vít Jelínek, Jan Kyncl

Hardness of Permutation Pattern Matching

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

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time

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

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances

Micha Sharir, Noam Solomon

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances

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

Spanning Circuits in Regular Matroids

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh

Spanning Circuits in Regular Matroids

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

Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time

Roee David, Uriel Feige

Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time

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

Stochastic k-Center and j-Flat-Center Problems

Lingxiao Huang, Jian Li

Stochastic k-Center and j-Flat-Center Problems

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

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

Anupam Gupta, Viswanath Nagarajan, Sahil Singla

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

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

Sample-Optimal Density Estimation in Nearly-Linear Time

Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt

Sample-Optimal Density Estimation in Nearly-Linear Time

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

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers

Chaya Keller, Shakhar Smorodinsky, Gábor Tardos

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers

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

Approximately Sampling Elements with Fixed Rank in Graded Posets

Prateek Bhakta, Ben Cousins, Matthew Fahrbach, Dana Randall

Approximately Sampling Elements with Fixed Rank in Graded Posets

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

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

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

Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz

Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

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

LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs

Nikhil Bansal, Daniel Reichman, Seeun William Umboh

LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs

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

Fair Coin Flipping: Tighter Analysis and the Many-Party Case

Niv Buchbinder, Iftach Haitner, Nissan Levi, Eliad Tsfadia

Fair Coin Flipping: Tighter Analysis and the Many-Party Case

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

LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

Daniel Prusa, Tomás Werner

LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

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

Better Approximations for Tree Sparsity in Nearly-Linear Time

Arturs Backurs, Piotr Indyk, Ludwig Schmidt

Better Approximations for Tree Sparsity in Nearly-Linear Time

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

Generalized Preconditioning and Undirected Minimum-Cost Flow

Jonah Sherman

Generalized Preconditioning and Undirected Minimum-Cost Flow

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

Totally Unimodular Congestion Games

Alberto Del Pia, Michael Ferris, Carla Michini

Totally Unimodular Congestion Games

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

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

Thomas D. Ahle, Martin Aumüller, Rasmus Pagh

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

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

Computing minimum cuts in hypergraphs

Chandra Chekuri, Chao Xu

Computing minimum cuts in hypergraphs

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

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

Robert Hildebrand, Robert Weismantel, Rico Zenklusen

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

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

Linear Size Distance Preservers

Greg Bodwin

Linear Size Distance Preservers

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

Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang

Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

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

Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications

Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams

Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications

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

Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

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

A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering

Tobias Christiani

A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering

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

Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold

Éric Colin de Verdière, Salman Parsa

Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold

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

Local Flow Partitioning for Faster Edge Connectivity

Monika Henzinger, Satish Rao, Di Wang

Local Flow Partitioning for Faster Edge Connectivity

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

Sorting from Noisier Samples

Aviad Rubinstein, Shai Vardi

Sorting from Noisier Samples

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

On the insertion time of random walk cuckoo hashing

Alan M. Frieze, Tony Johansson

On the insertion time of random walk cuckoo hashing

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

The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete

Paul C. Bell, Mika Hirvensalo, Igor Potapov

The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete

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

On Estimating Maximum Matching Size in Graph Streams

Sepehr Assadi, Sanjeev Khanna, Yang Li

On Estimating Maximum Matching Size in Graph Streams

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

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs

Aaron Bernstein, Shiri Chechik

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs

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

Permutation Property Testing under Different Metrics with Low Query Complexity

Jacob Fox, Fan Wei

Permutation Property Testing under Different Metrics with Low Query Complexity

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

Time-Space Trade-offs in Population Protocols

Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, Ronald L. Rivest

Time-Space Trade-offs in Population Protocols

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

On Rationality of Nonnegative Matrix Factorization

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell

On Rationality of Nonnegative Matrix Factorization

Details
Author Comments: The artifact is a worksheet in the "Maple classic worksheet" format (mws), which we used with Maple 8.
Discussion Comments: 0
Sharing: Research produced artifacts
Verification: Authors have verified information

Opting Into Optimal Matchings

Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish

Opting Into Optimal Matchings

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

LAST but not Least: Online Spanners for Buy-at-Bulk

Anupam Gupta, R. Ravi, Kunal Talwar, Seeun William Umboh

LAST but not Least: Online Spanners for Buy-at-Bulk

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

Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Pavel Hubácek, Eylon Yogev

Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

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

Approximation and Kernelization for Chordal Vertex Deletion

Bart M. P. Jansen, Marcin Pilipczuk

Approximation and Kernelization for Chordal Vertex Deletion

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

Testing for Forbidden Order Patterns in an Array

Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler

Testing for Forbidden Order Patterns in an Array

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

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack

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

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack

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

Computing Walrasian Equilibria: Fast Algorithms and Structural Properties

Renato Paes Leme, Sam Chiu-wai Wong

Computing Walrasian Equilibria: Fast Algorithms and Structural Properties

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

Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

Sam Chiu-wai Wong

Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

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

Playing Anonymous Games using Simple Strategies

Yu Cheng, Ilias Diakonikolas, Alistair Stewart

Playing Anonymous Games using Simple Strategies

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

Faster Sublinear Algorithms using Conditional Sampling

Themistoklis Gouleakis, Christos Tzamos, Manolis Zampetakis

Faster Sublinear Algorithms using Conditional Sampling

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

An Efficient Representation for Filtrations of Simplicial Complexes

Jean-Daniel Boissonnat, Karthik C. S.

An Efficient Representation for Filtrations of Simplicial Complexes

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

Make Up Your Mind: The Price of Online Queries in Differential Privacy

Mark Bun, Thomas Steinke, Jonathan Ullman

Make Up Your Mind: The Price of Online Queries in Differential Privacy

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

The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein

The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

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

Tight Network Topology Dependent Bounds on Rounds of Communication

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Tight Network Topology Dependent Bounds on Rounds of Communication

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

Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals

Nicole Immorlica, Robert Kleinberg, Brendan Lucier, Morteza Zadomighaddam

Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals

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

Explicit Resilient Functions Matching Ajtai-Linial

Raghu Meka

Explicit Resilient Functions Matching Ajtai-Linial

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

Low-Rank PSD Approximation in Input-Sparsity Time

Kenneth L. Clarkson, David P. Woodruff

Low-Rank PSD Approximation in Input-Sparsity Time

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

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

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

Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

Yixin Cao, R. B. Sandeep

Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

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

Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search

Sariel Har-Peled, Sepideh Mahabadi

Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search

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

Metric embeddings with outliers

Anastasios Sidiropoulos, Dingkang Wang, Yusu Wang

Metric embeddings with outliers

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

Scaling Algorithms for Weighted Matching in General Graphs

Ran Duan, Seth Pettie, Hsin-Hao Su

Scaling Algorithms for Weighted Matching in General Graphs

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

Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs

Bernhard Haeupler, David G. Harris

Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs

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

(1 + ∊)-Approximate f-Sensitive Distance Oracles

Shiri Chechik, Sarel Cohen, Amos Fiat, Haim Kaplan

(1 + ∊)-Approximate f-Sensitive Distance Oracles

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

Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube

Paul Beame, Cyrus Rashtchian

Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube

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

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

Michael Elkin, Ofer Neiman

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

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

Faster approximation schemes for the two-dimensional knapsack problem

Sandy Heydrich, Andreas Wiese

Faster approximation schemes for the two-dimensional knapsack problem

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

A Logarithmic Additive Integrality Gap for Bin Packing

Rebecca Hoberg, Thomas Rothvoss

A Logarithmic Additive Integrality Gap for Bin Packing

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

Faster Online Matrix-Vector Multiplication

Kasper Green Larsen, R. Ryan Williams

Faster Online Matrix-Vector Multiplication

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

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

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

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

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

Find Your Place: Simple Distributed Algorithms for Community Detection

Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan

Find Your Place: Simple Distributed Algorithms for Community Detection

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

Doubly Balanced Connected Graph Partitioning

Saleh Soltan, Mihalis Yannakakis, Gil Zussman

Doubly Balanced Connected Graph Partitioning

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

Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

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

A Hybrid Sampling Scheme for Triangle Counting

John Kallaugher, Eric Price

A Hybrid Sampling Scheme for Triangle Counting

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

Online and Random-order Load Balancing Simultaneously

Marco Molinaro

Online and Random-order Load Balancing Simultaneously

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

Partitioning a Graph into Small Pieces with Applications to Path Transversal

Euiwoong Lee

Partitioning a Graph into Small Pieces with Applications to Path Transversal

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

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)

Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)

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

Approximation Algorithms for Label Cover and The Log-Density Threshold

Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan

Approximation Algorithms for Label Cover and The Log-Density Threshold

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

Maximum Scatter TSP in Doubling Metrics

László Kozma, Tobias Mömke

Maximum Scatter TSP in Doubling Metrics

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

pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems

Arnab Ganguly, Rahul Shah, Sharma V. Thankachan

pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems

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

About the Structure of the Integer Cone and its Application to Bin Packing

Klaus Jansen, Kim-Manuel Klein

About the Structure of the Integer Cone and its Application to Bin Packing

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

Building a Good Team: Secretary Problems and the Supermodular Degree

Moran Feldman, Rani Izsak

Building a Good Team: Secretary Problems and the Supermodular Degree

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

An FPTAS for Counting Proper Four-Colorings on Cubic Graphs

Pinyan Lu, Kuan Yang, Chihao Zhang, Minshen Zhu

An FPTAS for Counting Proper Four-Colorings on Cubic Graphs

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

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces

Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert T. Schweller, Luis Vega, Tim Wylie

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces

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

Best-Response Dynamics in Combinatorial Auctions with Item Bidding

Paul Dütting, Thomas Kesselheim

Best-Response Dynamics in Combinatorial Auctions with Item Bidding

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

Strong Connectivity in Directed Graphs under Failures, with Applications

Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis

Strong Connectivity in Directed Graphs under Failures, with Applications

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

An Improved Upper Bound for the Universal TSP on the Grid

George Christodoulou, Alkmini Sgouritsa

An Improved Upper Bound for the Universal TSP on the Grid

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

When and Why the Topological Coverage Criterion Works

Nicholas J. Cavanna, Kirk P. Gardner, Donald R. Sheehy

When and Why the Topological Coverage Criterion Works

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

Optimal Approximate Polytope Membership

Sunil Arya, Guilherme Dias da Fonseca, David M. Mount

Optimal Approximate Polytope Membership

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

Core congestion is inherent in hyperbolic networks

Victor Chepoi, Feodor F. Dragan, Yann Vaxès

Core congestion is inherent in hyperbolic networks

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

Counting matchings in irregular bipartite graphs and random lifts

Marc Lelarge

Counting matchings in irregular bipartite graphs and random lifts

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

A tight bound for Green's arithmetic triangle removal lemma in vector spaces

Jacob Fox, László Miklós Lovász

A tight bound for Green's arithmetic triangle removal lemma in vector spaces

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

Better upper bounds on the Füredi-Hajnal limits of permutations

Josef Cibulka, Jan Kyncl

Better upper bounds on the Füredi-Hajnal limits of permutations

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

Algorithmic and Hardness Results for the Hub Labeling Problem

Haris Angelidakis, Yury Makarychev, Vsevolod Oparin

Algorithmic and Hardness Results for the Hub Labeling Problem

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

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

Christoph Berkholz, Martin Grohe

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

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

Online Lower Bounds via Duality

Yossi Azar, Ilan Reuven Cohen, Alan Roytman

Online Lower Bounds via Duality

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

Reordering Buffers with Logarithmic Diameter Dependency for Trees

Matthias Englert, Harald Räcke

Reordering Buffers with Logarithmic Diameter Dependency for Trees

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

Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

Optimal induced universal graphs for bounded-degree graphs

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

A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

Ami Paz, Gregory Schwartzman

A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

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

Iterative Partial Rounding for Vertex Cover with Hard Capacities

Mong-Jen Kao

Iterative Partial Rounding for Vertex Cover with Hard Capacities

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

Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling

Michael B. Cohen, Cameron Musco, Christopher Musco

Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling

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

Sandpile prediction on a tree in near linear time

Akshay Ramachandran, Aaron Schild

Sandpile prediction on a tree in near linear time

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

Fast and Memory-Efficient Algorithms for Evacuation Problems

Miriam Schlöter, Martin Skutella

Fast and Memory-Efficient Algorithms for Evacuation Problems

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

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

Christos Kalaitzis, Ola Svensson, Jakub Tarnawski

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

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

ETH Hardness for Densest-k-Subgraph with Perfect Completeness

Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein

ETH Hardness for Densest-k-Subgraph with Perfect Completeness

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

A constant-time algorithm for middle levels Gray codes

Torsten Mütze, Jerri Nummenpalo

A constant-time algorithm for middle levels Gray codes

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

Sampling on the Sphere by Mutually Orthogonal Subspaces

Uri Grupel

Sampling on the Sphere by Mutually Orthogonal Subspaces

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

LP-branching algorithms based on biased graphs

Magnus Wahlström

LP-branching algorithms based on biased graphs

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

Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

Moses Charikar, Vaggos Chatziafratis

Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

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

Approximation Algorithms for Finding Maximum Induced Expanders

Shayan Oveis Gharan, Alireza Rezaei

Approximation Algorithms for Finding Maximum Induced Expanders

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

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

Ittai Abraham, Shiri Chechik, Sebastian Krinninger

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

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

The Complexity of Simulation and Matrix Multiplication

Massimo Cairo, Romeo Rizzi

The Complexity of Simulation and Matrix Multiplication

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

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

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

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

Eden Chlamtác, Michael Dinitz, Yury Makarychev

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

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

Robust algorithms with polynomial loss for near-unanimity CSPs

Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal

Robust algorithms with polynomial loss for near-unanimity CSPs

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

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

Michele Borassi, Pierluigi Crescenzi, Luca Trevisan

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

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

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance

Timothy Naumovitz, Michael E. Saks, C. Seshadhri

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance

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

A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

Karl Bringmann

A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

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

Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration

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

High-dimensional approximate r-nets

Georgia Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros

High-dimensional approximate r-nets

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

Computing the Fréchet Distance between Real-Valued Surfaces

Kevin Buchin, Tim Ophelders, Bettina Speckmann

Computing the Fréchet Distance between Real-Valued Surfaces

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

Cross-Referenced Dictionaries and the Limits of Write Optimization

Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, Meng-Tsung Tsai

Cross-Referenced Dictionaries and the Limits of Write Optimization

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

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth

Venkatesan Guruswami, Ankit Singh Rawat

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth

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

Fair Scheduling via Iterative Quasi-Uniform Sampling

Sungjin Im, Benjamin Moseley

Fair Scheduling via Iterative Quasi-Uniform Sampling

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

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities

Shi Li

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities

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

Geodesic Spanners for Points on a Polyhedral Terrain

Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji

Geodesic Spanners for Points on a Polyhedral Terrain

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

A Framework for Analyzing Resparsification Algorithms

Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva

A Framework for Analyzing Resparsification Algorithms

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

An O(nm) time algorithm for finding the min length directed cycle in a graph

James B. Orlin, Antonio Sedeño-Noda

An O(nm) time algorithm for finding the min length directed cycle in a graph

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

On the Configuration-LP of the Restricted Assignment Problem

Klaus Jansen, Lars Rohwedder

On the Configuration-LP of the Restricted Assignment Problem

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

Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich

Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

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

Random cluster dynamics for the Ising model is rapidly mixing

Heng Guo, Mark Jerrum

Random cluster dynamics for the Ising model is rapidly mixing

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

Simplex Transformations and the Multiway Cut Problem

Niv Buchbinder, Roy Schwartz, Baruch Weizman

Simplex Transformations and the Multiway Cut Problem

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

Random Contractions and Sampling for Hypergraph and Hedge Connectivity

Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi

Random Contractions and Sampling for Hypergraph and Hedge Connectivity

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

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

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

Local Search for Max-Sum Diversification

Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen

Local Search for Max-Sum Diversification

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

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time

Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time

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

O(depth)-Competitive Algorithm for Online Multi-level Aggregation

Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Ohad Talmon

O(depth)-Competitive Algorithm for Online Multi-level Aggregation

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

Exploring an Infinite Space with Finite Memory Scouts

Lihi Cohen, Yuval Emek, Oren Louidor, Jara Uitto

Exploring an Infinite Space with Finite Memory Scouts

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

Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

Yossi Azar, Ashish Chiplunkar, Haim Kaplan

Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

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

Near-Optimal (Euclidean) Metric Compression

Piotr Indyk, Tal Wagner

Near-Optimal (Euclidean) Metric Compression

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

Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density

Sebastian Morr

Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density

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

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

Vitaly Feldman, Cristobal Guzman, Santosh Vempala

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

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

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

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

Approximating Multicut and the Demand Graph

Chandra Chekuri, Vivek Madan

Approximating Multicut and the Demand Graph

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

Distributed Degree Splitting, Edge Coloring, and Orientations

Mohsen Ghaffari, Hsin-Hao Su

Distributed Degree Splitting, Edge Coloring, and Orientations

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

Sequential measurements, disturbance and property testing

Aram Wettroth Harrow, Cedric Yen-Yu Lin, Ashley Montanaro

Sequential measurements, disturbance and property testing

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

LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs

Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli

LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs

Details
Author Comments:
Discussion Comments: 0
Sharing: Not able to share produced artifacts
Verification: Authors have verified information

Decidability of the Membership Problem for 2 × 2 integer matrices

Igor Potapov, Pavel Semukhin

Decidability of the Membership Problem for 2 × 2 integer matrices

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