On relations between counting communication complexity classes (Q1880784): Difference between revisions

We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established

0 references

zbMATH Keywords

Communication complexity class

0 references

Protocol

0 references

Non-determinism

0 references

Probabilism

0 references

Modularity

0 references

Upper bound

0 references

Lower bound

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.jcss.2004.03.002

0 references

cites work

Meanders and their applications in lower bounds arguments

0 references

Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs

0 references

Relativized counting classes: Relations among thresholds, parity, and mods

0 references

Q4195937

0 references

Relations between communication complexity classes

0 references

On the power of small-depth threshold circuits

0 references

Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits

0 references

Non-deterministic communication complexity with few witnesses

0 references

On the power of generalized Mod-classes

0 references

Geometric arguments yield better bounds for threshold circuits and distributed computing

0 references

On oblivious branching programs of linear length

0 references

Communication Complexity

0 references

Q4231904

0 references

Q5203681

0 references

Complexity classes defined by counting quantifiers

0 references

Q3737571

0 references

Identifiers

zbMATH Open document ID

1159.68465

0 references

DOI

10.1016/j.jcss.2004.03.002

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1880784

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2004.03.002
+Normal rank
@@ Property / OpenAlex ID @@
+W2018302254
@@ Property / OpenAlex ID: W2018302254 / rank @@
+Normal rank
@@ Property / cites work @@
+Meanders and their applications in lower bounds arguments
+Normal rank
@@ Property / cites work @@
+Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
+Normal rank
@@ Property / cites work @@
+Relativized counting classes: Relations among thresholds, parity, and mods
+Normal rank
@@ Property / cites work @@
+Q4195937
@@ Property / cites work: Q4195937 / rank @@
+Normal rank
@@ Property / cites work @@
+Relations between communication complexity classes
+Normal rank
@@ Property / cites work @@
+On the power of small-depth threshold circuits
@@ Property / cites work: On the power of small-depth threshold circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
+Normal rank
@@ Property / cites work @@
+Non-deterministic communication complexity with few witnesses
+Normal rank
@@ Property / cites work @@
+On the power of generalized Mod-classes
@@ Property / cites work: On the power of generalized Mod-classes / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric arguments yield better bounds for threshold circuits and distributed computing
+Normal rank
@@ Property / cites work @@
+On oblivious branching programs of linear length
@@ Property / cites work: On oblivious branching programs of linear length / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4231904
@@ Property / cites work: Q4231904 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5203681
@@ Property / cites work: Q5203681 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity classes defined by counting quantifiers
+Normal rank
@@ Property / cites work @@
+Q3737571
@@ Property / cites work: Q3737571 / rank @@
+Normal rank