Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR21-066 | 5th May 2021
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Dimension-free Bounds and Structural Results in Communication Complexity

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

TR21-065 | 5th May 2021
Nikhil Mande, Swagato Sanyal

One-way communication complexity and non-adaptive decision trees

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

TR21-064 | 5th May 2021
Noah Singer, Madhu Sudan, Santhoshini Velusamy

Streaming approximation resistance of every ordering CSP

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>

Next next

ISSN 1433-8092 | Imprint