Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with affine subspaces:
TR10-044 | 12th March 2010
Eli Ben-Sasson, Swastik Kopparty

Affine Dispersers from Subspace Polynomials

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

TR14-114 | 27th August 2014
Roei Tell

An Alternative Proof of an $\Omega(k)$ Lower Bound for Testing $k$-linear Boolean Functions

We provide an alternative proof for a known result stating that $\Omega(k)$ queries are needed to test $k$-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affi ne subspaces of the Boolean hypercube. ... more >>>

TR14-115 | 27th August 2014
Roei Tell

Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

TR22-082 | 27th May 2022
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

Low-Degree Polynomials Extract from Local Sources

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

TR22-104 | 18th July 2022
Nader Bshouty

On One-Sided Testing Affine Subspaces

Revisions: 1

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>

ISSN 1433-8092 | Imprint