Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with direct products:
TR13-179 | 15th December 2013
Irit Dinur, David Steurer

Direct Product Testing

A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>

TR14-047 | 8th April 2014
Mark Braverman, Omri Weinstein

An Interactive Information Odometer with Applications

Revisions: 1

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, ... more >>>

ISSN 1433-8092 | Imprint