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

The Communication Complexity of Enumeration, Elimination, and Selection

โœ Scribed by Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Torenvliet

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
278 KB
Volume
63
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let k, n ยฅ N and f: {0, 1} n ร— {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k ยฅ {0, 1} n , Bob has y 1 , ..., y k ยฅ {0, 1} n , and they want to compute

municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomized version of ELC for these functions.

(e) Under a reasonable (but unproven) assumption, the elimination problem for f 2 requires W(D(f)) bits, where D(f) is the deterministic complexity of f. This links a weak version of ELC to other assumptions.

๐Ÿ“œ SIMILAR VOLUMES

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)

The Importance of Complexity in Model Se
The Importance of Complexity in Model Selection
โœ In Jae Myung ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 152 KB

Model selection should be based not solely on goodness-of-fit, but must also consider model complexity. While the goal of mathematical modeling in cognitive psychology is to select one model from a set of competing models that best captures the underlying mental process, choosing the model that best

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
โœ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm

An implicit enumeration scheme for the b
An implicit enumeration scheme for the batch selection problem
โœ A. Agnetis; F. Rossi; S. Smriglio ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 135 KB

## Abstract An important problem arising in the management of logistic networks is the following: given a set of activities to be performed, each requiring a set of resources, select the optimal set of resources compatible with the system capacity constraints. This problem is called Batch Selection

Comparison of Forward Selection, Backwar
Comparison of Forward Selection, Backward Elimination, and Generalized Simulated Annealing for Variable Selection
โœ J.M. Sutter; J.H. Kalivas ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 360 KB

In order to obtain quantitative information, it is often necessary for a chemist to employ regression methods. An algorithm is described for determining the optimal subset of variables which gives the best prediction in regression analysis. The procedure is based on the generalized simulated anneali