We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle functi...
详细信息
We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle function f : L-m -> F-q, where L subset of F-q, a verifier distinguishes whether f is the evaluation of a low-degree polynomial or is far (in relative Hamming distance) from being one, by making only a few queries to f. This topic has been studied in the context of locally testable codes, interactive proofs, probalistically checkable proofs, and interactive oracle proofs. We present the first interactive oracle proofs of proximity (IOPP) for tensor products of Reed-Solomon codes (evaluation of polynomials with bounds on individual degrees) and for Reed-Muller codes (evaluation of polynomials with a bound on the total degree) that simultaneously achieve logarithmic query complexity, logarithmic verification time, linear oracle proof length and linear prover running time. Such low-degree polynomials play a central role in constructions of probabilistic proof systems and succinct non-interactive arguments of knowledge with zero-knowledge. For these applications, highly-efficient multivariate low-degree tests are desired, but prior probabilistic proofs of proximity required super-linear proving time. In contrast, for multivariate codes of length N, our constructions admit a prover running in time linear in N and a verifier which is logarithmic in N. Our constructions are directly inspired by the IOPP for Reed-Solomon codes of [Ben-Sasson et al., ICALP 2018] named "FRI protocol". Compared to the FRI protocol, our IOPP for tensor products of Reed-Solomon codes achieves the same efficiency parameters. As for Reed-Muller codes, for fixed constant number of variables m, the concrete efficiency of our IOPP for Reed-Muller codes compares well, all things equal.
We define a general framework of partition games for formulating two-player pebble games over finite structures. The framework we introduce includes as special cases the pebble games for finite-variable logics with an...
详细信息
We define a general framework of partition games for formulating two-player pebble games over finite structures. The framework we introduce includes as special cases the pebble games for finite-variable logics with and without counting. It also includes a matrix-equivalence game, introduced here, which characterises equivalence in the finite-variable fragments of the matrix-rank logic of [Dawar et al. 2009]. We show that one particular such game in our frame-work, which we call the invertible-map game, yields a family of polynomial-time approximations of graph isomorphism that is strictly stronger than the well-known Weisfeiler-Leman method. We show that the equivalence defined by this game is a refinement of the equivalence defined by each of the games for finite-variable logics.
Proposed is a fast context-adaptive binary arithmetic coding (CABAC) rate estimation method which can reduce the computational complexity of rate calculation for mode decision. The time-consuming CABAC rate calculatio...
详细信息
Proposed is a fast context-adaptive binary arithmetic coding (CABAC) rate estimation method which can reduce the computational complexity of rate calculation for mode decision. The time-consuming CABAC rate calculation for mode decision is simplified by using a proposed look-up table indexed only by the probability state index and the most probable symbol. Experimental results show that the proposed scheme is very effective in simplifying the binary arithmetic coding process for rate calculation since it achieves run-time saving of about 19.56% (up to 23.80%) with no degradation compared to the conventional method.
Array codes are the preferred codes for distributed storage, such that different rows in an array are stored at different nodes. Layered codes use a sparse format for stored arrays with a single parity check per colum...
详细信息
Array codes are the preferred codes for distributed storage, such that different rows in an array are stored at different nodes. Layered codes use a sparse format for stored arrays with a single parity check per column and no other parity checks. Remarkably, the simple structure of layered codes is optimal when data is collected from all but one node. Codes that collect data from fewer nodes include improved layered codes, determinant codes, cascade codes and moulin codes. As our main result we show that the concatenation of layered codes with suitable outer codes achieves the performance of cascade and moulin codes which is conjectured to be optimal for general regenerating codes. The codes that we use as outer codes are in a new class of codes that we call Johnson graph codes. The codes have properties similar to those of Reed-Muller codes. In both cases the topological structure of the set of coordinates can be used to identify information sets and codewords of small weight.
In this work, the correspondence between linear (n, k, d) codes and aperiodic convolution algorithms for computing a system phi of k bilinear forms over GF(p(m)) is explored. A number of properties are established for...
详细信息
In this work, the correspondence between linear (n, k, d) codes and aperiodic convolution algorithms for computing a system phi of k bilinear forms over GF(p(m)) is explored. A number of properties are established for the linear codes that can be obtained from a computational procedure of this type. A particular bilinear form is considered and a class of linear codes over GF(2m) is derived with varying k and d parameters. The code length n is equal to the multiplicative complexity of the computation of an aperiodic convolution and an efficient computation thereof leads to the shortest codes possible using this approach, many of which are optimal or near-optimal. A new decoding procedure for this class of linear codes is presented which exploits the block structure of the generator matrix of the codes. Several interesting observations are made on the nature of the codes obtained as a result of such computations. Such a computation of bilinear forms can be generalized to include other bilinear forms and the related classes of codes.
作者：
Kovacsics, Pablo CubidesDelon, FrancoiseUniv Lille
Unite Mixte Rech 8524 Lab Paul Painleve F-59655 Villeneuve Dascq France CNRS
F-59655 Villeneuve Dascq France Univ Paris Diderot
Unite Mixte Rech 7586 Inst Math Jussieu Paris Rive Gauche Equipe Log Math F-75205 Paris 13 France CNRS
Unite Format & Rech Math F-75205 Paris 13 France
In [15], Marker and Steinhorn characterized models M = 1 that there is a pair M < N of algebraically closed valued fields such that all n-types over M realized in N are definable but there is an n + 1-type over M r...
详细信息
In [15], Marker and Steinhorn characterized models M < N of an o-minimal theory such that all types over M realized in N are definable. In this article we characterize pairs of algebraically closed valued fields satisfying the same property. In o-minimal theories, a pair of models M < N for which all 1-types over M realized in N are definable has already the desired property. Although it is true that if M is an algebraically closed valued field such that all 1-types over M are definable then all types over M are definable, we build a counterexample for the relative statement, i.e., we show for any n >= 1 that there is a pair M < N of algebraically closed valued fields such that all n-types over M realized in N are definable but there is an n + 1-type over M realized in N which is not definable. (C) 2016 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
A triply even code is a binary linear code in which the weight of every codeword is divisible by 8. We show how two doubly even codes of lengths m(1) and m(2) can be combined to make a triply even code of length m(1)+...
详细信息
A triply even code is a binary linear code in which the weight of every codeword is divisible by 8. We show how two doubly even codes of lengths m(1) and m(2) can be combined to make a triply even code of length m(1)+m(2), and then prove that every maximal triply even code of length 48 can be obtained by combining two doubly even codes of length 24 in a certain way. Using this result, we show that there are exactly ten maximal triply even codes of length 48 up to equivalence.
Let H be a pointed Hopf algebra. We show that under some mild assumptions H and its associated graded Hopf algebra gr H have the same Gelfand-Kirillov dimension (GK-dimension). As an application, we prove that the GK-...
详细信息
Let H be a pointed Hopf algebra. We show that under some mild assumptions H and its associated graded Hopf algebra gr H have the same Gelfand-Kirillov dimension (GK-dimension). As an application, we prove that the GK-dimension of a connected Hopf algebra is either infinity or a positive integer. We also classify connected Hopf algebras of GK-dimension 3 over an algebraically closed field of characteristic 0.
Subspace designs are a (large) collection of high-dimensional subspaces {H-i- of F-q(m) such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection ...
详细信息
Subspace designs are a (large) collection of high-dimensional subspaces {H-i- of F-q(m) such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection with W;more precisely, the sum of dimensions of W boolean AND H-i is at most some parameter L. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica '16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed Solomon codes and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound L on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F-n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log logn)).
Let F be the function field of a smooth, geometrically integral curve over a p-adic field with p not equal 2. In this paper we show that if G is an absolutely simple adjoint algebraic group over F of type (2)A(n)*, C-...
详细信息
Let F be the function field of a smooth, geometrically integral curve over a p-adic field with p not equal 2. In this paper we show that if G is an absolutely simple adjoint algebraic group over F of type (2)A(n)*, C-n, or D-n, (D-4 non-trialitarian) such that the associated hermitian form has even rank, trivial discriminant (if G is of type (2)A(n)* or D-n) and trivial Clifford invariant (if G is of type D-n) then the group of rational equivalence classes, G(F)/R is trivial. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论