All reports by Author Dmytro Gavinsky:

__
TR24-009
| 20th January 2024
__

Dmytro Gavinsky#### Unambiguous parity-query complexity

Comments: 1

__
TR23-166
| 5th November 2023
__

Dmytro Gavinsky#### Patterned non-determinism in communication complexity

__
TR17-123
| 2nd August 2017
__

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR15-137
| 22nd August 2015
__

Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito#### On the Role of Shared Randomness in Simultaneous Communication

__
TR14-011
| 22nd January 2014
__

Dmytro Gavinsky, Pavel Pudlak#### Partition Expanders

__
TR13-190
| 28th December 2013
__

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR13-080
| 4th June 2013
__

Dmytro Gavinsky, Shachar Lovett#### En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

__
TR13-044
| 25th March 2013
__

Dmytro Gavinsky, Tsuyoshi Ito, Guoming Wang#### Shared Randomness and Quantum Communication in the Multi-Party Model

__
TR12-051
| 25th April 2012
__

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan#### A Tail Bound for Read-k Families of Functions

__
TR10-165
| 4th November 2010
__

Dmytro Gavinsky, Tsuyoshi Ito#### Quantum Fingerprints that Keep Secrets

__
TR10-060
| 5th April 2010
__

Dmytro Gavinsky, Alexander A. Sherstov#### A Separation of NP and coNP in Multiparty Communication Complexity

__
TR07-074
| 7th August 2007
__

Dmytro Gavinsky, Pavel Pudlak#### Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

__
TR07-058
| 9th June 2007
__

Dmytro Gavinsky#### Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

__
TR06-086
| 25th July 2006
__

Dmytro Gavinsky, Julia Kempe, Ronald de Wolf#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

Dmytro Gavinsky

We give a lower bound of ?(?n) on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over {0,1}? whose value is "0" if the Hamming weight of the input is at most n/3, is "1" if ... more >>>

Dmytro Gavinsky

We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by $PNP^{X\leftrightarrow Y}$.

It generalises the known models $UP^{X\leftrightarrow Y}$ and $FewP^{X\leftrightarrow Y}$ through relaxing the constraints on the witnessing structure of the underlying $NP^{X\leftrightarrow Y}$-protocol.

It is shown that for the case of total functions ...
more >>>

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito

Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits.

It allows the parties to act in a correlated manner, which can be quite useful.

But what happens if the shared randomness is not perfect?

In this work, ... more >>>

Dmytro Gavinsky, Pavel Pudlak

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is required that the number of edges between any ... more >>>

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

Dmytro Gavinsky, Shachar Lovett

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... more >>>

Dmytro Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>Dmytro Gavinsky, Tsuyoshi Ito

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. No classical fingerprinting scheme is hiding. We construct quantum hiding fingerprinting schemes and argue their optimality.

more >>>Dmytro Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

Dmytro Gavinsky, Pavel Pudlak

We give the first exponential separation between quantum and

classical multi-party

communication complexity in the (non-interactive) one-way and

simultaneous message

passing settings.

For every k, we demonstrate a relational communication problem

between k parties

that can be solved exactly by a quantum simultaneous message passing

protocol of

cost ...
more >>>

Dmytro Gavinsky

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>Dmytro Gavinsky, Julia Kempe, Ronald de Wolf

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>