Characterizing linear size circuits in terms of privacy

DOI10.1006/jcss.1997.1544zbMath0938.68048OpenAlexW1988394435MaRDI QIDQ1305927

Eyal Kushilevitz, Adi Rosén, Rafail Ostrovsky

Publication date: 22 September 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1544

zbMATH Keywords

complexity class\(n\)-party private protocols

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Lower and upper bounds on the randomness complexity of private computations of AND ⋮ Random sources in private computation ⋮ Privacy in non-private environments ⋮ Unnamed Item ⋮ Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND

Cites Work

• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• A Boolean function requiring 3n network size
• Randomness in private computations
• Privacy and Communication Complexity
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Private Computations over the Integers
• Randomness vs. fault-tolerance
• A Zero-One Law for Boolean Privacy

This page was built for publication: Characterizing linear size circuits in terms of privacy