Non-deterministic communication complexity with few witnesses

Mauricio Karchmer; Mike Saks; Ilan Newman; Avi Wigderson

Non-deterministic communication complexity with few witnesses

Mauricio Karchmer, Mike Saks, Ilan Newman, Avi Wigderson

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

Abstract

Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for n_k(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that n_k(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds n_k(f) by log(rk(M_f))/k-1, where rk(M_f) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

Original language	English (US)
Title of host publication	Proceedings of the Seventh Annual Structure in Complexity Theory Conference
Publisher	Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516
Pages	275-281
Number of pages	7
ISBN (Print)	081862955X
State	Published - 1992
Externally published	Yes
Event	Proceedings of the Seventh Annual Structure in Complexity Theory Conference - Boston, MA, USA Duration: Jun 22 1992 → Jun 25 1992

Publication series

Name	Proceedings of the Seventh Annual Structure in Complexity Theory Conference

Other

Other	Proceedings of the Seventh Annual Structure in Complexity Theory Conference
City	Boston, MA, USA
Period	6/22/92 → 6/25/92

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@inproceedings{e4ee4a1d2ffd4651b34b4c013a55f83c,

title = "Non-deterministic communication complexity with few witnesses",

abstract = "Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for nk(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that nk(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds nk(f) by log(rk(Mf))/k-1, where rk(Mf) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.",

author = "Mauricio Karchmer and Mike Saks and Ilan Newman and Avi Wigderson",

note = "Funding Information: In the two-party communication complexity model, two parties compute a function that depends on both of their (initially private) inputs. Roughly speaking, the deterministic communication complexity of a function f(x, y) is the minimum * Supported by NSF Grant CCR90-10533. t This work was done while the author was at the Royal Instituut of Technology, Stockholm. Supported in part by NSF Grant CCR89-11388, and AFOSR Grants 89-0512B and 90-0008.; Proceedings of the Seventh Annual Structure in Complexity Theory Conference ; Conference date: 22-06-1992 Through 25-06-1992",

year = "1992",

language = "English (US)",

isbn = "081862955X",

series = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

publisher = "Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516",

pages = "275--281",

booktitle = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

}

Karchmer, M, Saks, M, Newman, I & Wigderson, A 1992, Non-deterministic communication complexity with few witnesses. in Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, pp. 275-281, Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, MA, USA, 6/22/92.

Non-deterministic communication complexity with few witnesses. / Karchmer, Mauricio; Saks, Mike; Newman, Ilan et al.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, 1992. p. 275-281 (Proceedings of the Seventh Annual Structure in Complexity Theory Conference).

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

TY - GEN

T1 - Non-deterministic communication complexity with few witnesses

AU - Karchmer, Mauricio

AU - Saks, Mike

AU - Newman, Ilan

AU - Wigderson, Avi

N1 - Funding Information: In the two-party communication complexity model, two parties compute a function that depends on both of their (initially private) inputs. Roughly speaking, the deterministic communication complexity of a function f(x, y) is the minimum * Supported by NSF Grant CCR90-10533. t This work was done while the author was at the Royal Instituut of Technology, Stockholm. Supported in part by NSF Grant CCR89-11388, and AFOSR Grants 89-0512B and 90-0008.

PY - 1992

Y1 - 1992

N2 - Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for nk(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that nk(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds nk(f) by log(rk(Mf))/k-1, where rk(Mf) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

AB - Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for nk(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that nk(f) is bounded below by Ω(√c(f)/k) where c(f) is the deterministic complexity. A second result bounds nk(f) by log(rk(Mf))/k-1, where rk(Mf) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

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

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

M3 - Conference contribution

AN - SCOPUS:0027099111

SN - 081862955X

T3 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

SP - 275

EP - 281

BT - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

PB - Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516

T2 - Proceedings of the Seventh Annual Structure in Complexity Theory Conference

Y2 - 22 June 1992 through 25 June 1992

ER -

Non-deterministic communication complexity with few witnesses

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this