Publication

Some constructions of maximal witness codes

2011
Conference Papers

Abstract

Given a code C is an element of F-2(n) and a word c is an element of C, a witness of c is a subset W subset of {, 1 ... , n} of coordinate positions such that c differs from any other codeword c' is an element of C on the indices in W. If any codeword posseses a witness of given length w, C is called a w-witness code. This paper gives new constructions of large w-witness codes and proves with a numerical method that their sizes are maximal for certain values of n and w. Our technique is in the spirit of Delsarte's linear programming bound on the size of classical codes and relies on the Lovasz theta number, semidefinite programming, and reduction through symmetry.

Official source

https://infoscience.epfl.ch/entities/publication/759b9b6a-1a2f-4cfc-a840-e080cab8ca70

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2011
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/759b9b6a-1a2f-4cfc-a840-e080cab8ca70

About this result

Related concepts (32)

Cyclic code

In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction. Let be a linear code over a finite field (also called Galois field) of block length . is called a cyclic code if, for every codeword from , the word in obtained by a cyclic right shift of components is again a codeword.

Semidefinite programming

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Related publications (32)

Some constructions of maximal witness codes

Chat with Graph Search

Acceleration of Solvers for Plasma Simulation in the Tokamak Boundary

Semi-empirical universal model of heat capacity based on the Laplace distribution Напівемпірична універсальна модель теплоємності на основі розподілу Лапласа

Efficient Krylov Methods for Linear Response in Plane-Wave Electronic Structure Calculations