id: 06083552
dt: a
an: 06083552
au: Lê, Dai Tri Man; Cook, Stephen A.; Ye, Yuli
ti: A formal theory for the complexity class associated with the stable
    marriage problem.
so: Bezem, Marc (ed.), Computer science logic (CSL’11). 25th international
    workshop, 20th annual conference of the EACSL, Bergen, Norway,
    September 12‒15, 2011. Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum
    für Informatik (ISBN 978-3-939897-32-3). LIPICS ‒ Leibniz
    International Proceedings in Informatics 12, 381-395, electronic only
    (2011).
py: 2011
pu: Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik
la: EN
cc: 
ut: bounded arithmetic; complexity theory; comparator circuits
ci: 
li: doi:10.4230/LIPIcs.CSL.2011.381
    http://subs.emis.de/LIPIcs/frontdoor_2d07.html
ab: Summary: Subramanian defined the complexity class CC as the set of problems
    log-space reducible to the comparator circuit value problem. He proved
    that several other problems are complete for CC, including the stable
    marriage problem, and finding the lexicographical first maximal
    matching in a bipartite graph. We suggest alternative definitions of CC
    based on different reducibilities and introduce a two-sorted theory
    VCC* based on one of them. We sharpen and simplify Subramanian’s
    completeness proofs for the above two problems and formalize them in
    VCC*.
rv: