Alman, Josh ;
Vassilevska Williams, Virginia
OV Graphs Are (Probably) Hard Instances
Abstract
A graph G on n nodes is an Orthogonal Vectors (OV) graph of dimension d if there are vectors v_1, …, v_n ∈ {0,1}^d such that nodes i and j are adjacent in G if and only if ⟨v_i,v_j⟩ = 0 over Z. In this paper, we study a number of basic graph algorithm problems, except where one is given as input the vectors defining an OV graph instead of a general graph. We show that for each of the following problems, an algorithm solving it faster on such OV graphs G of dimension only d=O(log n) than in the general case would refute a plausible conjecture about the time required to solve sparse MAXkSAT instances:
 Determining whether G contains a triangle.
 More generally, determining whether G contains a directed kcycle for any k ≥ 3.
 Computing the square of the adjacency matrix of G over ℤ or 𝔽_2.
 Maintaining the shortest distance between two fixed nodes of G, or whether G has a perfect matching, when G is a dynamically updating OV graph.
We also prove some complementary results about OV graphs. We show that any problem which is NPhard on constantdegree graphs is also NPhard on OV graphs of dimension O(log n), and we give two problems which can be solved faster on OV graphs than in general: Maximum Clique, and Online MatrixVector Multiplication.
BibTeX  Entry
@InProceedings{alman_et_al:LIPIcs:2020:11768,
author = {Josh Alman and Virginia Vassilevska Williams},
title = {{OV Graphs Are (Probably) Hard Instances}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {83:183:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11768},
URN = {urn:nbn:de:0030drops117686},
doi = {10.4230/LIPIcs.ITCS.2020.83},
annote = {Keywords: Orthogonal Vectors, FineGrained Reductions, Cycle Finding}
}
06.01.2020
Keywords: 

Orthogonal Vectors, FineGrained Reductions, Cycle Finding 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 