The size and depth of layered Boolean circuits

DOI10.1016/j.ipl.2010.11.023zbMath1260.94093OpenAlexW1999374138MaRDI QIDQ1944075

Jing-Tang Jang, Anna Gál

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.023

zbMATH Keywords

computational complexityBoolean circuitscircuit depthcircuit sizepebble games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Sublinear-communication secure multiparty computation does not require FHE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speedups of deterministic machines by synchronous parallel machines
• An observation on time-storage trade off
• Circuit size is nonlinear in depth
• A separator theorem for graphs of bounded genus
• Simulation of Parallel Random Access Machines by Circuits
• The Size and Depth of Layered Boolean Circuits
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Space-bounded simulation of multitape turing machines
• A Separator Theorem for Nonplanar Graphs
• On Time Versus Space
• The Depth of All Boolean Functions
• On Relating Time and Space to Size and Depth
• Space bounds for a game on graphs
• An n logn Lower Bound on Synchronous Combinational Complexity
• Relations Among Complexity Measures

This page was built for publication: The size and depth of layered Boolean circuits