Testing Reed Muller Codes ∗ (2009)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector’s bits. We show that...
Typical Peak Sidelobe Level of Binary Sequences (2009)
Noga Alon, Simon Litsyn, Er Shpunt
Abstract. For a binary sequence Sn = {si: i = 1, 2,..., n} ∈ {±1} n, n> 1, the peak sidelobe level (PSL) is defined as M(Sn) = max k=1,2,...,n−1 | n−k ∑ sisi+k|. i=1 It is shown that the...
NEW UPPER BOUNDS ON CODES VIA ASSOCIATION SCHEMES AND LINEAR PROGRAMMING (2008)
Beniamin Mounits, Tuvi Etzion, Simon Litsyn
(Communicated by Eimear Byrne) Abstract. Let A(n, d) denote the maximum number of codewords in a binary code of length n and minimum Hamming distance d. Upper and lower bounds on A(n, d) have been a...
Testing low-degree polynomials over GF(2) (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract. We describe an efficient randomized algorithm to test if a given binary function � � ����� � � ���� � is a low-degree polynomial (that is, a sum of low-degree...
Testing low-degree polynomials over GF(2), booktitle (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥...
time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...
[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of
Exact minimum density of codes identifying vertices in the square grid (2008)
Abstract. An identifying code C is a subset of the vertices of the square grid Z 2 with the property that for each element v of Z 2, the collection of elements from C at a distance of at most one...
Estimates of the distance distribution of codes and designs (2008)
Alexei Ashikhmin, Er Barg, Simon Litsyn, Senior Member, Senior Member
Abstract—We consider the problem of bounding the distance distribution for unrestricted block codes with known distance and/or dual distance. Applying the polynomial method, we provide a general...
Bounds for Codes in Products of Spaces, Grassmann and Stiefel Manifolds (2008)
Christine Bachoc, Yael Ben-haim, Simon Litsyn, Senior Member
Upper bounds are derived for codes in Stiefel and Grassmann manifolds with given minimum chordal distance. They stem from upper bounds for codes in the product of unit spheres and projective spaces....
Testing low-degree polynomials over (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn
Abstract. We describe an efficient randomized algorithm to test if a given binary function is a low-degree polynomial (that is, a sum of low-degree monomials). For a ���� � given integer...
Iiro Honkala, Tero Laihonen, Simon Litsyn
Abstract We derive a new upper bound on the covering radius of a code as a function of its dual distance. This bound improves on the Honkala-Litsyn-Tiet"av"ainen bound and in a...
Abstract We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Breaking the $epsilon$-Soundness Bound of the Linearity Test over GF(2) (2008)
Kaufman, Tali, Litsyn, Simon, Xie, Ning
For Boolean functions that are $epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested...
School of Mathematical Sciences, (2007)
We derive new estimates for the range where the distance distribution of a code is upperbounded by the corresponding normalized binomial distribution. The estimates depend on the code's dual...
Binary B_2-Sequences: a new upper bound (2007)
We show that the maximum size of a B_2-sequence of binary n-vectors for large enough n is at most 2^0.5753n, thus improving on the previous bound 2^0.6n due to B. Lindström.
Linear Programming Bounds for Codes of Small Size (2007)
Combining linear programming approach with the Plotkin-Johnson argument for constant weight codes, we derive upper bounds on the size of codes of length n and minimum distance d = (n 0 j)=2, 0 ! j !...
Parameters of Goppa codes revisited (2007)
Françoise Levy-dit-Vehel, Simon Litsyn
We discuss parameters of Goppa codes, such as minimum distance, covering radius, distance distribution, and generalized Hamming weights. By a variation on the exponential sums method and...
Asymptotically Exact Bounds on the Size of High-Order Spectral-Null Codes (2007)
The spectral-null code S(n; k) of k-th order and length n is the union of n-tuples with \Sigma1 components, having k-th order spectral null at zero frequency. We determine the exact asymptotic in n...
On Distribution of Exponential Sums in Fields of Characteristic Two (2007)
Distribution of the values of exponential sums in finite fields of characteristic two is considered. We derive upper bounds on the individual components of this distribution. 1 Introduction Let F = F...
On the covering radius of long Goppa codes (2007)
Françoise Levy-Dit-Vehel, Simon Litsyn
Introduction The covering radius is an important parameter of error-correcting codes [2]. It coincides with the maximal multiplicity of errors that can be corrected provided the maximum likelihood...
More on the covering radius of BCH codes (2007)
Francoise Levy-dit-Vehel, Simon Litsyn
New lower bounds on the minimum length of t-error correcting BCH codes with covering radius at most 2t are derived. Keywords: covering radius, BCH codes, systems of equations over finite fields. I....
Short dominating paths and cycles in the binary (2007)
Uri Blass, Iiro Honkala, Mark G. Karpovsky, Simon Litsyn
hypercube
Iiro Honkala, Mark G. Karpovsky, Simon Litsyn
A set of subgraphs C1, C2,..., Ck in a graph G is said to identify
Noga Alon, Michael Krivelevich, Simon Litsyn
hashing and applications to digital ngerprinting
Bounds for codes in products of spaces, Grassmann and Stiefel manifolds (2006)
Bachoc, Christine, Ben-Haim, Yael, Litsyn, Simon
Upper bounds are derived for codes in Stiefel and Grassmann manifolds with given minimal chordal distance. They stem from upper bounds for codes in products of unit spheres and projective spaces. The...
New Upper Bounds on A(n,d) (2005)
Mounits, Beniamin, Etzion, Tuvi, Litsyn, Simon
Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
A Lower Bound on the Density of Sphere Packings via Graph Theory (2004)
Krivelevich, Michael, Litsyn, Simon, Vardy, Alexander
Using graph-theoretic methods we give a new proof that for all sufficiently large $n$, there exist sphere packings in $\R^n$ of density at least $cn2^{-n}$, exceeding the classical Minkowski bound by...
Testing Reed Muller Codes \Lambda (2004)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits....
A lower bound on the density of sphere packings via graph theory (2004)
Krivelevich, Michael, Litsyn, Simon, Vardy, Alexander
Using graph-theoretic methods we give a new proof that for all sufficiently large n, there exist sphere packings in ℝn of density at least cn2−n exceeding the classical Minkowski bound by a...
on distance distributions in codes of given size (2003)
Michael Krivelevich, Simon Litsyn
We prove a new upper bound on the possible distance distribution of a code of a given size. The main instrument of the proof is the Beckner inequality from Harmonic Analysis. We also show that the...
Generalized Hashing and Parent-Identifying Codes (2003)
Noga Alon, Gerard Cohen, Michael Krivelevich, Simon Litsyn
Let C be a code of length n over an alphabet of q letters. For a pair of integers 2 t < u, C is (t; u)-hashing if for any two subsets T ; U C, satisfying T U , jT j = t, jU j = u, there is a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Improved upper bounds on sizes of codes (2002)
Beniamin Mounits, Tuvi Etzion, Simon Litsyn, Senior Member, Senior Member
Abstract—Let @ A denote the maximum possible number of codewords in a binary code of length and minimum Hamming distance. For large values of, the best known upper bound, for fixed, is the Johnson...
Upper bounds on the rate of LDPC codes (2002)
David Burshtein, Michael Krivelevich, Simon Litsyn, Gadi Miller
We derive upper bounds on the rate of low density parity check (LDPC) codes for which reliable communication is achievable. We rst generalize Gallager's bound to a general binaryinput...
Short Dominating Paths and Cycles in the Binary Hypercube (2001)
Uri Blass, Iiro Honkala, Mark G. Karpovsky, Simon Litsyn
Introduction Denote by F the binary alphabet, and by F n the space of binary vectors of length n endowed with the Hamming metric d(\Delta; \Delta), i.e., the binary hypercube. The covering radius of...
Quantum Error Detection I: Statement of the Problem (1999)
Ashikhmin, Alexei, Barg, Alexander, Knill, Emanuel, Litsyn, Simon
I. This paper is devoted to the problem of error detection with quantum codes. In the first part we examine possible problem settings for quantum error detection. Our goal is to derive a functional...
Improved estimates on covering radius (1999)
Ashikhmin, Alexei, Honkala, Iiro, Laihonen, Tero, Litsyn, Simon
On relations between covering radius and dual distance (1999)
Ashikhmin, Alexei, Honkala, Iiro, Laihonen, Tero, Litsyn, Simon
The Smallest Covering Code of Length 8 and Radius 2 Has 12 Words (1999)
We prove that the smallest covering code of length 8 and covering radius 2 has exactly 12 words. The proof is based on partial classification of even weight codewords, followed by a search for small...
Several New Lower Bounds for Football Pool Systems (1999)
We derive several new lower bounds on the size of ternary covering codes of lengths 6, 7 and 8 and with covering radii 2 or 3. 1 Introduction Ternary covering code C of length n and radius R is a...
More on the distance distribution of BCH codes (1999)
We derive a new estimate for the error term in the binomial approximation to the distance distribution of BCH codes. This is an improvement on the earlier bounds by Kasami-Fujiwara-Lin,...
On binary constructions of quantum codes (1998)
Cohen, Gérard, Encheva, Sylvia, Litsyn, Simon
Using the notion of generalized weight we improve estimates on the parameters of quantum codes obtained by Steane's construction from binary codes. This yields several new families of quantum codes.
Codes correcting phased burst erasures (1998)
We introduce a family of binary array codes of size t2n, correcting multiple phased burst erasures of size t. The codes achieve maximal correcting capability, i.e. being considered as codes over GF(2...
Bounds on Spectra of Codes with Known Dual Distance (1998)
. We estimate the interval where the distance distribution of a code of length n and of given dual distance is upperbounded by the binomial distribution. The binomial upper bound is shown to be sharp...
Upper Bounds on the Size of Quantum Codes (1997)
Ashikhmin, Alexei, Litsyn, Simon
Several upper bounds on the size of quantum codes are derived using the linear programming approach. These bounds are strengthened for the linear quantum codes.
On covering radius and discrete Chebyshev polynomials (1997)
Honkala, Iiro, Laihonen, Tero, Litsyn, Simon
http://www.tucs.fi/Publications/journals/jHoLaLi97.php
Linear Programming Bounds for Doubly-Even Self-Dual Codes (1997)
We give a new proof of the Mallows-Sloane bound on the minimum distance of doubly-even self-dual codes. The proof avoids using the Gleason theorem and invariant theory. It is based on a special...
On upper bounds for minimum distance and covering radius of non-binary codes (1996)
http://www.tucs.fi/Publications/techreports/TR80.php
On covering radius and discrete Chebyshev polynomials (1996)
Honkala, Iiro, Laihonen, Tero, Litsyn, Simon
http://www.tucs.fi/Publications/techreports/TR81.php
On the Traveling Salesman Problem in Binary Hamming Spaces (1996)
Gérard Cohen, Simon Litsyn, Gilles Zémor, Gilles Z Emor
Given a subset X of vertices in the n-cube, i.e. the n-dimensional Hamming space, we are interested in the solution for the traveling salesman problem, namely the minimal length of a cycle passing...
A Class of Array Codes Correcting Multiple Column Erasures (1996)
A family of binary array codes of size (p01)2n, for a prime p, correcting multiple column erasures is proposed. The codes achieve the maximum possible correcting capability. Complexity of encoding...
On Greedy Algorithms in Coding Theory (1996)
Gérard Cohen, Simon Litsyn, Gilles Zémor, Gilles Z'emor
We study a wide class of problems in coding theory for which we consider two different formulations: in terms of incidence matrices and in terms of hypergraphs. These problems are dealt with using a...
On Integral Zeros of Krawtchouk Polynomials (1996)
We derive new conditions for nonexistence of integral zeros of binary Krawtchouk polynomials. Upper bounds for the number of integral roots of Krawtchouk polynomials are presented. Keywords:...
Weighted coverings and packings (1995)
Cohen, Gérard, Honkala, Iiro, Litsyn, Simon, Mattson Jr, H. F.
Bounds for binary codes that are multiple coverings of the farthest-off points (1995)
Hämäläinen, Heikki, Honkala, Iiro, Litsyn, Simon, ÃstergÃ¥rd, Patric
Football pools - a game for mathematicians (1995)
Hämäläinen, Heikki, Honkala, Iiro, Litsyn, Simon, ÃstergÃ¥rd, Patric
On Accuracy of Binomial Approximation to the Distance Distribution of Codes (1995)
The binomial distribution is a well known approximation to the distance spectra of many classes of codes. We derive a lower estimate for the deviation from the binomial approximation. Keywords:...
On Spectra of BCH Codes (1995)
We derive an estimate for the error term in the binomial approximation of spectra of BCH codes. This estimate asymptotically improves on the earlier bounds by Sidelnikov, Kasami-Fujiwara-Lin and...
Weighted coverings and packings (1994)
Cohen, Gérard, Honkala, Iiro, Litsyn, Simon, Mattson Jr, H. F.
New Upper Bounds on Error Exponents
We derive new upper bounds on the error exponents for the maximum likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the straight-line bound by...
An Improved Upper Bound on the Minimum Distance of Doubly-Even Self-Dual Codes
We derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives lim n!1 sup d=n (5 \Gamma 5 3=4 )=10 ! 0:165630, thus...