Category Archives: Coding Theory

Constructing blocking sets using expander graphs and hypergraphs

Posted on November 19, 2024 by Anurag Bishnoi

Blocking sets are one of the central topics in finite geometry, which was originally introduced in the context of game theory under the name of `blocking coalitions’: On Finite Projective Games. I first learned about them during my Ph.D. as … Continue reading →

A new upper bound on the trifference problem

Posted on February 13, 2024 by Anurag Bishnoi

In a recent preprint, Siddharth Bhandari and Abhishek Khetan have improved the decades old upper bound on the trifference problem by using a clever combinatorial argument involving extremal graph theory. As discussed in my previous posts a trifferent code of … Continue reading →

Posted in Coding Theory, Extremal Combinatorics | Tagged Bhandari, combinatorics, extremal problems, Khetan, mathematics, research, trifference, trifferent, trifferent codes | Leave a comment

Strong blocking sets and minimal codes from expander graphs

Posted on May 25, 2023 by Anurag Bishnoi

Finite geometry is often used to construct graphs with certain extremal properties. For example, the Norm graphs are one of the best-known constructions in extremal graph theory (see this for a geometrical description of these graphs). Similarly, generalized polygons, and … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Spectral Graph Theory | Tagged algebraic-geometric codes, blocking set, construction, expander mixing lemma, expanders, extremal problems, finite geometry, minimal codes, ramanujan graphs, strong blocking sets | 1 Comment

Explicit trifferent codes via concatenation

Posted on March 23, 2023 by Anurag Bishnoi

Recall that a trifferent code is a set of ternary codewords with the property that for any three codewords in there is a coordinate position where they all have pairwise distinct values. Moreover, if is a vector subspace, then it … Continue reading →

Posted in Coding Theory, Combinatorics, Finite Geometry | Tagged algebraic-geometric codes, alon, blocking set, combinatorics, concatenated codes, explicit construction, extremal problems, finite fields, finite geometry, linear trifferent codes, trifference, trifferent | 1 Comment

Sets of points meeting each subspace in a few points

Posted on March 15, 2023 by Anurag Bishnoi

In the real plane, a set of points is said to be in general position if no three of them lie on a line. The same notion can be defined for higher dimensional spaces by calling a set of points … Continue reading →

Posted in Coding Theory, Finite Geometry | Tagged arcs, blocking set, cap-set, combinatorics, finite fields, finite geometry, generalized hamming distance, hamming distance, hitting set, linear codes, progression-free set, sidon set, subspace design, subspace evasive, weight hirerachy | Leave a comment

Linear trifferent codes and minimal codes

Posted on January 24, 2023 by Anurag Bishnoi

In the previous post, we saw the problem of determining the asymptotic growth of the function , which is the largest size of vector subspace , with the property that for any three distinct vectors in , there is a … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics | Tagged combinatorics, finite fields, finite geometry, linear trifferent codes, minimal codes, trifference | 1 Comment

The Trifference Problem

Posted on January 23, 2023 by Anurag Bishnoi

What is the largest possible size of a set of ternary strings of length , with the property that for any three distinct strings in , there is a position where they all differ? Let denote this largest size. Trivially, … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry | Tagged blocking set, combinatorics, extremal problems, finite fields, finite geometry, trifference, trifferent | 4 Comments

A coding theoretic application of the Alon-Füredi theorem

Posted on March 7, 2021 by Anurag Bishnoi

The Alon-Füredi theorem is something that I have written a lot about in this blog. I spent a considerable amount of time on this theorem during my PhD. In fact, it’s generalisation that I obtained and it’s applications in finite … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method | Tagged Alon-Furedi, finite fields, finite geometry, linear codes, minimal codes, polynomials | 4 Comments

The footprint bound

Posted on March 25, 2018 by Anurag Bishnoi

Studying the set of common zeros of systems of polynomial equations is a fundamental problem in algebra and geometry. In this post we will look at estimating the cardinality of the set of common zeros, when we already know that … Continue reading →

Posted in Coding Theory, Combinatorics, Polynomial Method | Tagged algebraic geometry, Alon-Furedi, combinatorial nullstellensatz, combinatorics, finite fields, footprint, Groebner basis, standard monomials | 1 Comment