14 citations · 48 across the 28 of their papers we have counts for
4 papers · 1 filter
A Formula for the Determinant
Nicholas Pippenger
We give a formula for the determinant of an matrix with entries from a commutative ring with unit. The formula can be evaluated by a "straight-line program" performing…
Gap Theorems for the Delay of Circuits Simulating Finite Automata
Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger
We study the delay (also known as depth) of circuits that simulate finite automata, showing that only certain growth rates (as a function of the number of steps simulated) are…
Local versus Global Search in Channel Graphs
A. H. Hunter, Nicholas Pippenger
Previous studies of search in channel graphs has assumed that the search is global; that is, that the status of any link can be probed by the search algorithm at any time. We consi…
Attribute Estimation and Testing Quasi-Symmetry
Krzysztof Majewski, Nicholas Pippenger
A Boolean function is symmetric if it is invariant under all permutations of its arguments; it is quasi-symmetric if it is symmetric with respect to the arguments on which it actua…