Under the auspices of the Computational Complexity Foundation (CCF)

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

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