Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with finite fields:
TR00-041 | 19th May 2000
Igor E. Shparlinski

Security of Polynomial Transformations of the Diffie--Hellman Key

D. Boneh and R. Venkatesan have recently proposed an approach to proving
that a reasonably small portions of most significant bits of the
Diffie--Hellman key modulo a prime are as secure the the whole key. Some
further improvements and generalizations have been obtained by
I. M. Gonzales Vasco ... more >>>

TR07-056 | 10th July 2007
Zeev Dvir, Ariel Gabizon, Avi Wigderson

Extractors and Rank Extractors for Polynomial Sources

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

TR09-004 | 15th January 2009
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... more >>>

TR09-037 | 10th April 2009
Parikshit Gopalan

A Fourier-analytic approach to Reed-Muller decoding

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

TR10-092 | 22nd May 2010
Charanjit Jutla, Arnab Roy

A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

Revisions: 1 , Comments: 1

We consider multivariate pseudo-linear functions
over finite fields of characteristic two. A pseudo-linear polynomial
is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards
and a single linear term, and each linear-guard is
again a linear term but raised ... more >>>

TR11-054 | 13th April 2011
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Tight lower bounds for 2-query LCCs over finite fields

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

TR12-014 | 20th February 2012
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

TR12-044 | 22nd April 2012
Swastik Kopparty

List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

TR12-049 | 27th April 2012
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

Sparse affine-invariant linear codes are locally testable

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

TR12-180 | 21st December 2012
Chaim Even-Zohar, Shachar Lovett

The Freiman-Ruzsa Theorem in Finite Fields

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.
The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$
then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ... more >>>

TR13-126 | 11th September 2013
Arman Fazeli, Shachar Lovett, Alex Vardy

Nontrivial t-designs over finite fields exist for all t

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

TR14-010 | 23rd January 2014
Jean Bourgain, Zeev Dvir, Ethan Leeman

Affine extractors over large fields with exponential error

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

more >>>

TR15-077 | 4th May 2015
Arnab Bhattacharyya, Abhishek Bhowmick

Using higher-order Fourier analysis over general fields

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>

TR15-109 | 1st July 2015
Mrinal Kumar, Ramprasad Saptharishi

An exponential lower bound for homogeneous depth-5 circuits over finite fields

In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in N\}$ of polynomials in $VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, ... more >>>

TR18-047 | 7th March 2018
Shachar Lovett

A proof of the GM-MDS conjecture

Revisions: 1

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.

more >>>

TR19-042 | 18th March 2019
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Determinant equivalence test over finite fields and over $\mathbf{Q}$

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>

ISSN 1433-8092 | Imprint