๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Communication complexity of convex optimization

โœ Scribed by John N Tsitsiklis; Zhi-Quan Luo

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
692 KB
Volume
3
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider a situation where each of two processors has access to a different convex functionA, i = 1,2, defined on a common bounded domain. The processors are to exchange a number of binary messages, according to some protocol, until they find a point in the domain at which f, + h is minimized, within some prespecified accuracy E. Our objective is to determine protocols under which the number of exchanged messages is minimized. 0 1987 Academic Press. Inc.

๐Ÿ“œ SIMILAR VOLUMES

Communication Complexity of Gossiping by
Communication Complexity of Gossiping by Packets
โœ Luisa Gargano; Adele A. Rescigno; Ugo Vaccaro ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 153 KB

This paper considers the problem of gossiping with packets of limited size in a network with a cost function. We show that the problem of determining the minimum cost necessary to perform gossiping among a given set of participants with packets of limited size is NP-hard. We also give an approximate

The Communication Complexity of Pointer
The Communication Complexity of Pointer Chasing
โœ Stephen J. Ponzio; Jaikumar Radhakrishnan; S. Venkatesh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 253 KB

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity 7, 109 127) showed an upper bound of O(n log (k&1) n) for this problem. We prove a matching lower bound; this improves the lower bound of 0(n)