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.Expand abstract
We explore two techniques that have hitherto found little to no applications in this theory. They build upon...
- Publication status:
- Peer review status:
- Peer reviewed
- Publisher's version
- Schloss Dagstuhl Publisher's website
- Publication date:
- Acceptance date:
- Pubs id:
- Local pid:
- Copyright holder:
- Chistikov et al.
- Copyright date:
- © Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, Jeffrey Shallit. This article was presented at STACS 2017: 34th International Symposium on Theoretical Aspects of Computer Science (March 8-11, 2017: Hannover, Germany). Licensed under Creative Commons License CC-BY.
Fractional coverings, greedy coverings, and rectifier networks
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record