Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Compression:
TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

We initiate the study of the compressibility of NP problems. We
consider NP problems that have long instances but relatively
short witnesses. The question is, can one efficiently compress an
instance and store a shorter representation that maintains the
information of whether the original input is in the language or
more >>>

TR06-080 | 16th June 2006
David Doty

Dimension Extractors

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>

TR10-057 | 1st April 2010
Scott Aaronson, Andrew Drucker

A Full Characterization of Quantum Advice

Revisions: 3

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

TR10-083 | 13th May 2010
Mark Braverman, Anup Rao

Efficient Communication Using Partial Information

Revisions: 1

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.

We ... more >>>

TR11-069 | 18th April 2011
Marius Zimand

On the optimal compression of sets in PSPACE

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

TR13-024 | 7th February 2013
Valentine Kabanets, Antonina Kolokolova

Compression of Boolean Functions

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

TR14-101 | 8th August 2014
Balthazar Bauer, Shay Moran, Amir Yehudayoff

Internal compression of protocols to entropy

Revisions: 1

We study internal compression of communication protocols
to their internal entropy, which is the entropy of the transcript from the players' perspective.
We first show that errorless compression to the internal entropy
(and hence to the internal information) is impossible.
We then provide two internal compression schemes with error.
One ... more >>>

TR14-113 | 27th August 2014
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication for Boolean Functions

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

TR14-165 | 3rd December 2014
Venkatesan Guruswami, Ameya Velingker

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

TR15-051 | 5th April 2015
Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

TR15-088 | 31st May 2015
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Communication and External Information

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

TR15-092 | 31st May 2015
Yael Tauman Kalai, Ilan Komargodski

Compressing Communication in Distributed Protocols

Revisions: 1

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

ISSN 1433-8092 | Imprint