NDLI: Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Please wait, while we are loading the content...

Approximate Distance Oracles with Improved Bounds

Proof of the Satisfiability Conjecture for Large k

Preserving Statistical Validity in Adaptive Data Analysis

Randomized Composable Core-sets for Distributed Submodular Maximization

On the Lovász Theta function for Independent Sets in Sparse Graphs

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

Indistinguishability Obfuscation for Turing Machines with Unbounded Memory

Sketching and Embedding are Equivalent for Norms

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm

Exponential Separation of Information and Communication for Boolean Functions

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method

Excluded Grid Theorem: Improved and Simplified

Random Permutations using Switching Networks

Learning Arbitrary Statistical Mixtures of Discrete Distributions

Approximate k-flat Nearest Neighbor Search

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree

Consistency Thresholds for the Planted Bisection Model

Local, Private, Efficient Protocols for Succinct Histograms

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

The Complexity of the Simplex Method

Rectangles Are Nonnegative Juntas

Quantum Information Complexity

Approximating the Nash Social Welfare with Indivisible Items

Succinct Garbling and Indistinguishability Obfuscation for RAM Programs

Prioritized Metric Structures and Embedding

Quantum Spectrum Testing

FPTAS for #BIS with Degree Bounds on One Side

Lower Bounds on the Size of Semidefinite Programming Relaxations

High Parallel Complexity Graphs and Memory-Hard Functions

The Directed Grid Theorem

Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Tight Bounds for Learning a Mixture of Two Gaussians

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Minimizing Flow-Time on Unrelated Machines

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

On the Complexity of Random Satisfiability Problems with Planted Solutions

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Sparse Quantum Codes from Quantum Circuits

On the Complexity of Nash Equilibria in Anonymous Games

Succinct Randomized Encodings and their Applications

Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space

2-Server PIR with Sub-Polynomial Communication

Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

Testing Cluster Structure of Graphs

Learning Mixtures of Gaussians in High Dimensions

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

Randomized Rounding for the Largest Simplex Problem

Clustered Integer 3SUM via Additive Combinatorics

Sum-of-squares Lower Bounds for Planted Clique

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

$L_{p}$ Row Sampling by Lewis Weights

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

The List Decoding Radius of Reed-Muller Codes over Small Fields

Small Value Parallel Repetition for General Games

Hardness of Graph Pricing Through Generalized Max-Dicut

Garbled RAM From One-Way Functions

A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds

Test-and-Set in Optimal Space

Beyond the Euler Characteristic: Approximating the Genus of General Graphs

Solving the Shortest Vector Problem in $2^{n}$ Time Using Discrete Gaussian Sampling: Extended Abstract

Efficiently Learning Ising Models on Arbitrary Graphs

From Independence to Expansion and Back Again

Greedy Algorithms for Steiner Forest

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

Sum of Squares Lower Bounds from Pairwise Independence

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate

A Characterization of the Capacity of Online (causal) Binary Channels

An Interactive Information Odometer and Applications

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Non-malleable Reductions and Applications

Adjacency Labeling Schemes and Induced-Universal Graphs

Computing with Tangles

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

Secretary Problems with Non-Uniform Arrival Order

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Inapproximability of Combinatorial Problems via Small LPs and SDPs

Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Reed-Muller Codes for Random Erasures and Errors

The communication complexity of interleaved group products

Inapproximability of Nash Equilibrium

Leveled Fully Homomorphic Signatures from Standard Lattices

How Well Can Graphs Represent Wireless Interference?

Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract

Analysis of a Classical Matrix Preconditioning Algorithm

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Content Provider	ACM Digital Library
Author	Saranurak, Thatchaphol Krinninger, Sebastian Henzinger, Monika Nanongkai, Danupon
Abstract	Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by $v_{1},$ ., $v_{n},$ one by one. After seeing each vector $v_{i},$ we have to output the product $Mv_{i}$ before we can see the next vector. A naive algorithm can solve this problem using $O(n^{3})$ time in total, and its running time can be slightly improved to $O(n^{3}/log^{2}$ n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic $(O(n^{3-ε}))$ time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.
Starting Page	21
Ending Page	30
Page Count	10
File Format	PDF
ISBN	9781450335362
DOI	10.1145/2746539.2746609
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bounds Dynamic graph algorithms
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in