Abstract:
Let $M$ be a random $m \times n$ matrix with binary entries and i.i.d. rows. The weight (i.e., number of ones) of a row has a specified probability distribution, with the row chosen uniformly at random given its weight. Let $N(n,m)$ denote the number of left null vectors in ${0,1}^m$ for $M$ (including the zero vector), where addition is mod 2. We take $n, m \to \infty$, with $m/n \to \alpha > 0$, while the weight distribution may vary with $n$ but converges weakly to a limiting distribution on ${3, 4, 5, ...}$; let $W$ denote a variable with this limiting distribution. Identifying $M$ with a hypergraph on $n$ vertices, we define the 2-core of $M$ as the terminal state of an iterative algorithm that deletes every row incident to a column of degree 1. We identify two thresholds $\alpha^*$ and $\underline{\alpha}$, and describe them analytically in terms of the distribution of $W$. Threshold $\alpha^*$ marks the infimum of values of $\alpha$ at which $n^{-1} \log{\mathbb{E} [N(n,m)}]$ converges to a positive limit, while $\underline{\alpha}$ marks the infimum of values of $\alpha$ at which there is a 2-core of non-negligible size compared to $n$ having more rows than non-empty columns. We have $1/2 \leq \alpha^* \leq \underline{\alpha} \leq 1$, and typically these inequalities are strict; for example when $W = 3$ almost surely, numerics give $\alpha^* = 0.88949 ...$ and $\underline{\alpha} = 0.91793 ...$ (previous work on this model has mainly been concerned with such cases where $W$ is non-random). The threshold of values of $\alpha$ for which $N(n,m) \geq 2$ in probability lies in $[\alpha^*,\underline{\alpha}]$ and is conjectured to equal $\underline{\alpha}$. The random row weight setting gives rise to interesting new phenomena not present in the non-random case that has been the focus of previous work.

Abstract:
An identification scheme based on parity check matrix of error-correcting codes over GF(2) was proposed in the paper "A New Paradigm for Public Key Identification" by J. Stern(1996), a new identification scheme based on parity check matrix of rank distance codes over GF(qN) (q is a prime) is proposed in this paper, the limitation on the weight of mysterious datum s is changed into the limitation on the rank of s. It is proved that the given protocol is a zero-knowledge interactive proof in the random oracle model, and it is shown that the scheme is more secure than the scheme of J. Stern when parameters are selected properly.

Abstract:
Random linear systems over the Galois Field modulo 2 have an interest in connection with problems ranging from computational optimization to complex networks. They are often approached using random matrices with Poisson-distributed or finite column/row-sums. This technical note considers the typical rank of random matrices belonging to a specific ensemble wich has genuinely power-law distributed column-sums. For this ensemble, we find a formula for calculating the typical rank in the limit of large matrices as a function of the power-law exponent and the shape of the matrix, and characterize its behavior through "phase diagrams" with varying model parameters.

Abstract:
We study a conjecture called "linear rank conjecture" recently raised in (Tsang et al., FOCS'13), which asserts that if many linear constraints are required to lower the degree of a GF(2) polynomial, then the Fourier sparsity (i.e. number of non-zero Fourier coefficients) of the polynomial must be large. We notice that the conjecture implies a surprising phenomenon that if the highest degree monomials of a GF(2) polynomial satisfy a certain condition, then the Fourier sparsity of the polynomial is large regardless of the monomials of lower degrees -- whose number is generally much larger than that of the highest degree monomials. We develop a new technique for proving lower bound on the Fourier sparsity of GF(2) polynomials, and apply it to certain special classes of polynomials to showcase the above phenomenon.

Abstract:
We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-sparse GF(2) polynomial versus $\eps$-far from every such polynomial. Our algorithm makes $\poly(s,1/\eps)$ black-box queries to $f$ and runs in time $n \cdot \poly(s,1/\eps)$. The only previous algorithm for this testing problem \cite{DLM+:07} used poly$(s,1/\eps)$ queries, but had running time exponential in $s$ and super-polynomial in $1/\eps$. Our approach significantly extends the ``testing by implicit learning'' methodology of \cite{DLM+:07}. The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie \cite{SchapireSellie:96}. A crucial element of this work, which enables us to simulate the membership queries required by \cite{SchapireSellie:96}, is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of ``low-influence'' sets of variables.

Abstract:
Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random network coding. In this paper, we show that constant-rank codes are closely related to constant-dimension codes and we study the properties of constant-rank codes. We first introduce a relation between vectors in $\mathrm{GF}(q^m)^n$ and subspaces of $\mathrm{GF}(q)^m$ or $\mathrm{GF}(q)^n$, and use it to establish a relation between constant-rank codes and constant-dimension codes. We then derive bounds on the maximum cardinality of constant-rank codes with given rank weight and minimum rank distance. Finally, we investigate the asymptotic behavior of the maximal cardinality of constant-rank codes with given rank weight and minimum rank distance.

Abstract:
We show that, if $k$ and $\ell$ are positive integers and $r$ is sufficiently large, then the number of rank-$k$ flats in a rank-$r$ matroid $M$ with no $U_{2,\ell+2}$-minor is less than or equal to number of rank-$k$ flats in a rank-$r$ projective geometry over GF$(q)$, where $q$ is the largest prime power not exceeding $\ell$.

Abstract:
Four recursive constructions of permutation polynomials over $\gf(q^2)$ with those over $\gf(q)$ are developed and applied to a few famous classes of permutation polynomials. They produce infinitely many new permutation polynomials over $\gf(q^{2^\ell})$ for any positive integer $\ell$ with any given permutation polynomial over $\gf(q)$. A generic construction of permutation polynomials over $\gf(2^{2m})$ with o-polynomials over $\gf(2^m)$ is also presented, and a number of new classes of permutation polynomials over $\gf(2^{2m})$ are obtained.

Abstract:
The paper gives a succinct appraisal of the properties of the projective line defined over the direct product ring $R\_{\triangle} \equiv$ GF(2)$\otimesGF(2)\otimes$GF(2). The ring is remarkable in that except for unity, all the remaining seven elements are zero-divisors, the non-trivial ones forming two distinct sets of three; elementary ('slim') and composite ('fat'). Due to this fact, the line in question is endowed with a very intricate structure. It contains twenty-seven points, every point has eighteen neighbour points, the neighbourhoods of two distant points share twelve points and those of three pairwise distant points have six points in common -- namely those with coordinates having both the entries `fat' zero-divisors. Algebraically, the points of the line can be partitioned into three groups: a) the group comprising three distinguished points of the ordinary projective line of order two (the 'nucleus'), b) the group composed of twelve points whose coordinates feature both the unit(y) and a zero-divisor (the 'inner shell') and c) the group of twelve points whose coordinates have both the entries zero-divisors (the 'outer shell'). The points of the last two groups can further be split into two subgroups of six points each; while in the former case there is a perfect symmetry between the two subsets, in the latter case the subgroups have a different footing, reflecting the existence of the two kinds of a zero-divisor. The structure of the two shells, the way how they are interconnected and their link with the nucleus are all fully revealed and illustrated in terms of the neighbour/distant relation. Possible applications of this finite ring geometry are also mentioned.