Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LIFTING:
Reports tagged with Lifting:
TR12-106 | 27th August 2012

#### New affine-invariant codes from lifting

In this work we explore error-correcting codes derived from
the lifting'' of affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

TR12-149 | 8th November 2012
Alan Guo, Swastik Kopparty, Madhu Sudan

#### New affine-invariant codes from lifting

In this work we explore error-correcting codes derived from
the lifting'' of affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

TR13-030 | 20th February 2013

#### Absolutely Sound Testing of Lifted Codes

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

TR13-053 | 4th April 2013
Alan Guo

#### High rate locally correctable codes via lifting

Revisions: 1

We present a general framework for constructing high rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes of Guo, Kopparty, ... more >>>

TR17-029 | 18th February 2017
Clement Canonne, Tom Gur

#### An Adaptivity Hierarchy Theorem for Property Testing

Revisions: 1

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>>

TR19-103 | 7th August 2019

#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

TR20-099 | 6th July 2020
Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>> TR20-155 | 18th October 2020 Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan #### Log-rank and lifting for AND-functions Revisions: 1 Let$f: \{0,1\}^n \to \{0, 1\}$be a boolean function, and let$f_\land (x, y) = f(x \land y)$denote the AND-function of$f$, where$x \land y$denotes bit-wise AND. We study the deterministic communication complexity of$f_\land$and show that, up to a$\log n\$ factor, it is ... more >>>

ISSN 1433-8092 | Imprint