Relations Among Complexity Measures

By Nicholas Pippenger, Michael J. Fischer. 1979

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, background): “Standard results show that polynomially-sized circuits are equivalent (up to a logarithmic factor) to Turing machines that run in polynomial time [33], though of course the actual efficiency of computing via circuits versus on native hardware depends heavily on the application (e.”
On the Computational Efficiency of Training Neural Networks (2014, background): “The proof of the theorem relies on the result of [18] and is given in the appendix.”
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (2024, methodology): “Since any Turing Machine with time bound T ( n ) can be simulated by a circuit of size T ( n ) log T ( n ) (Pippenger & Fischer, 1979), we know that P ⊆ P / poly .”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “The constraint formalism is expressive: Degree-2 constraints can represent any computation that terminates in polynomial time (this is implied by Pippenger and Fischer’s result [47]).”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “The design in Zahur and Evans (2013), inspired by Pippenger and Fischer (1979), divides the stack into bu ers where the level-i bu er has 5 ⇥ 2i data slots.”
Verifying computations without reexecuting them (2015, background): “This transformation is possible because any of our computations p is naturally modeled by a Turing Machine (TM), and meanwhile a TM can be “unrolled” into a Boolean circuit that is not much larger than the number of steps in the computation [46].”
Privacy-preserving matrix factorization (2013, methodology): “In general, any RAM program executable in bounded time T can be converted to a O(T (3)) Turing machine [8], and any bounded T -time TM can be converted to a circuit of size O(T log T ) [54], which is dataoblivious.”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, result): “Combining this with the result of Pippenger and Fischer [80] that any T -step multi-tape Turing machine computation can be performed by an oblivious two-tape Turing machine in T(T log T ) steps, and the fact that the computation of an oblivious Turing machine (say with two tapes) in T ' steps can”
Checking the correctness of memories (1991, methodology): “We use an idea from the simulation by oblivious Turing machines of Pippenger and Fischer 16].”
On the Quality of the Initial Basin in Overspecified Neural Networks (2015, background): “on function. Propagating the input forward through the graph, the net returns its value via the output of the ﬁnal layer in the graph. Artiﬁcial neural nets are a known to have broad expressive power [17, 18, 20]. A recent breakthrough in the effectiveness of neural networks has led to very impressi”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, unknown): “CLP13 [7] (w/ oblivious queue [39,45,59]) O((D + log2 N) log2 N)!(1) 37.”
Issues in Multiagent Resource Allocation (2006, background): “second property is a consequence of the constructions presented by Schnorr [88] and Fischer and Pippenger [ 41 ].”
Oblivious RAM Revisited (2010, unknown): “This problem is related to the classic result of Pippenger and Fischer on oblivious simulation of Turing machines [18].”