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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>

The propositional proof system resolution over parities (Res($\oplus$)) combines resolution and the linear algebra over GF(2). It is a challenging open question to prove a superpolynomial lower bound on the proof size in this system. For many years, superpolynomial lower bounds were known only in tree-like cases. Recently, Efremenko, Garlik, ... more >>>

Razborov [J. ACM, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter $k = k(n)$, there exists $k$-CNF formulas over $n$ variables, having resolution refutations of $O(k)$ width, but every tree-like refutation of width $n^{1-\epsilon}/k$ needs size $\text{exp}\big(n^{\Omega(k)}\big)$. We extend this result to tree-like ... more >>>

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper (Beame, Koroth, 2023) introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that ... more >>>