On (Valiant’s) Polynomial-Size Monotone Formula for Majority

DOI10.1007/978-3-030-43662-9_3OpenAlexW3014441018MaRDI QIDQ5098767

Oded Goldreich

Publication date: 30 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.372.6965

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (3)

A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings ⋮ Computing majority by constant depth majority circuits with low fan-in gates

Cites Work

• Improved sorting networks with O(log N) depth
• Sorting in \(c \log n\) parallel steps
• Efficient Multiparty Protocols via Log-Depth Threshold Formulae
• Short monotone formulae for the majority function
• Unnamed Item

This page was built for publication: On (Valiant’s) Polynomial-Size Monotone Formula for Majority