Isolation, matching, and counting

E. Allender; K. Reinhardt

doi:10.1109/CCC.1998.694594

Isolation, matching, and counting

E. Allender, K. Reinhardt

School of Arts and Sciences, Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

Original language	English (US)
Title of host publication	Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998
Publisher	IEEE Computer Society
Pages	92-100
Number of pages	9
ISBN (Print)	0818683953
DOIs	https://doi.org/10.1109/CCC.1998.694594
State	Published - 1998
Event	13th Annual IEEE Conference on Computational Complexity, CCC 1998 - Buffalo, United States Duration: Jun 15 1998 → Jun 18 1998

Publication series

Name	Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)	1093-0159

Other

Other	13th Annual IEEE Conference on Computational Complexity, CCC 1998
Country/Territory	United States
City	Buffalo
Period	6/15/98 → 6/18/98

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.1998.694594

Cite this

@inproceedings{34f4a18c02c7473094f31de822f18d49,

title = "Isolation, matching, and counting",

abstract = "We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.",

author = "E. Allender and K. Reinhardt",

note = "Publisher Copyright: {\textcopyright} 1998 IEEE.; 13th Annual IEEE Conference on Computational Complexity, CCC 1998 ; Conference date: 15-06-1998 Through 18-06-1998",

year = "1998",

doi = "10.1109/CCC.1998.694594",

language = "English (US)",

isbn = "0818683953",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

publisher = "IEEE Computer Society",

pages = "92--100",

booktitle = "Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998",

address = "United States",

}

Allender, E & Reinhardt, K 1998, Isolation, matching, and counting. in Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998., 694594, Proceedings of the Annual IEEE Conference on Computational Complexity, IEEE Computer Society, pp. 92-100, 13th Annual IEEE Conference on Computational Complexity, CCC 1998, Buffalo, United States, 6/15/98. https://doi.org/10.1109/CCC.1998.694594

TY - GEN

T1 - Isolation, matching, and counting

AU - Allender, E.

AU - Reinhardt, K.

PY - 1998

Y1 - 1998

N2 - We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

AB - We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

UR - http://www.scopus.com/inward/record.url?scp=84947220454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947220454&partnerID=8YFLogxK

U2 - 10.1109/CCC.1998.694594

DO - 10.1109/CCC.1998.694594

M3 - Conference contribution

AN - SCOPUS:84947220454

SN - 0818683953

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 92

EP - 100

BT - Proceedings - 13th Annual IEEE Conference on Computational Complexity, CCC 1998

PB - IEEE Computer Society

T2 - 13th Annual IEEE Conference on Computational Complexity, CCC 1998

Y2 - 15 June 1998 through 18 June 1998

ER -

Isolation, matching, and counting

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this