Barrington plays cards: the complexity of card-based protocols

DOI10.4230/LIPICS.STACS.2021.26MaRDI QIDQ7231549zbMATH OpenFDO

Authors Pavel Dvořák, Michal Koucký

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.26

zbMATH Keywords

branching programefficient card-based protocolTuring machine

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Card-based cryptographic protocols using a minimal number of cards
• Card-based protocols for any Boolean function
• Card-based protocols for securely computing the conjunction of multiple variables
• Computations with a deck of cards
• Computing with a full memory: catalytic space
• Foundations for actively secure card-based cryptography
• scientific article; zbMATH DE number 1024066 (Why is no real title available?)
• More Efficient Match-Making and Satisfiability The Five Card Trick
• Necessary and sufficient numbers of cards for securely computing two-bit output functions
• Six-Card Secure AND and Four-Card Secure XOR
• The five-card trick can be done with four cards
• The minimum number of cards in practical card-based protocols

This page was built for publication: Barrington plays cards: the complexity of card-based protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231549)