Name
Title | ||
|---|---|---|
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness |
Abstract | ||
|---|---|---|
We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the ... |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/CCC.2005.1 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
multiparty nof communication complexity,finite ring,set disjointness,automorphism problem,integer factorization,direct sum theorem,protocols,frequency,broadcasting,rectangular distribution,set theory,communication complexity,computational complexity | Discrete mathematics,Average-case complexity,Set theory,Structural complexity theory,Computer science,Direct sum,Communication complexity,Descriptive complexity theory,Worst-case complexity,Corruption | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-2364-1 | 10 |
PageRank | References | Authors |
0.61 | 27 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Toniann Pitassi | 2 | 2282 | 155.18 |
| Nathan Segerlind | 3 | 223 | 11.22 |
| Avi Wigderson | 4 | 8205 | 1064.31 |