Chistikov, Dmitry ;
Iván, Szabolcs ;
Lubiw, Anna ;
Shallit, Jeffrey
Fractional Coverings, Greedy Coverings, and Rectifier Networks
Abstract
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix M that has a 1 in the entry (i,j) iff there is a path from the jth source to the ith sink. The smallest number of edges in a rectifier network that computes M is a classic complexity measure on matrices, which has been studied for more than half a century.
We explore two techniques that have hitherto found little to no applications in this theory. They build upon a basic fact that depth2 rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. Using fractional and greedy coverings (defined in the standard way), we obtain new results in this area.
First, we show that all fractional coverings of the socalled full triangular matrix have cost at least n log n. This provides (a fortiori) a new proof of the tight lower bound on its depth2 complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth2 complexity of the KneserSierpinski (disjointness) matrix. The previous upper bound is O(n^{1.28}), and we improve it to O(n^{1.17}), while the best known lower bound is Omega(n^{1.16}). Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unboundeddepth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
BibTeX  Entry
@InProceedings{chistikov_et_al:LIPIcs:2017:7010,
author = {Dmitry Chistikov and Szabolcs Iv{\'a}n and Anna Lubiw and Jeffrey Shallit},
title = {{Fractional Coverings, Greedy Coverings, and Rectifier Networks}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {23:123:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7010},
URN = {urn:nbn:de:0030drops70107},
doi = {10.4230/LIPIcs.STACS.2017.23},
annote = {Keywords: rectifier network, ORcircuit, biclique covering, fractional covering, greedy covering}
}
06.03.2017
Keywords: 

rectifier network, ORcircuit, biclique covering, fractional covering, greedy covering 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

06.03.2017 