Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with disjointness:
TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

One-way multi-party communication lower bound for pointer jumping with applications

In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th ... more >>>

TR08-002 | 19th December 2007
Arkadev Chattopadhyay, Anil Ada

Multiparty Communication Complexity of Disjointness

Revisions: 3

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

TR08-003 | 25th December 2007
Troy Lee, Adi Shraibman

Disjointness is hard in the multi-party number-on-the-forehead model

We show that disjointness requires randomized communication
in the general k-party number-on-the-forehead model of complexity.
The previous best lower bound was Omega(\frac{log n}{k-1}). By
results of Beame, Pitassi, and Segerlind, this implies
2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver
proof systems needed to refute certain unsatisfiable ... more >>>

TR12-061 | 16th May 2012
Pavel Hrubes, Amir Yehudayoff

Formulas are exponentially stronger than monotone circuits in non-commutative setting

We give an example of a non-commutative monotone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general ... more >>>

TR12-131 | 18th October 2012
Mark Braverman, Ankur Moitra

An Information Complexity Approach to Extended Formulations

Revisions: 1

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>>

TR12-153 | 9th November 2012
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Certifying Equality With Limited Interaction

Revisions: 1

The \textsc{equality} problem is usually one's first encounter with
communication complexity and is one of the most fundamental problems in the
field. Although its deterministic and randomized communication complexity
were settled decades ago, we find several new things to say about the
problem by focusing on two subtle aspects. The ... more >>>

TR12-171 | 3rd December 2012
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

From Information to Exact Communication

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

TR14-060 | 21st April 2014
Anup Rao, Amir Yehudayoff

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

more >>>

TR15-081 | 12th May 2015
Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

ISSN 1433-8092 | Imprint