Binary Non-tiles

Details Binary Non-tiles Binary Non-tiles

2009-11-07

arxiv.org/abs/0911.1388v2

Computer Science

Discrete Mathematics

Scientific paper

A subset V of GF(2)^n is a tile if GF(2)^n can be covered by disjoint translates of V. In other words, V is a tile if and only if there is a subset A of GF(2)^n such that V+A = GF(2)^n uniquely (i.e., v + a = v' + a' implies that v=v' and a=a' where v,v' in V and a,a' in A). In some problems in coding theory and hashing we are given a putative tile V, and wish to know whether or not it is a tile. In this paper we give two computational criteria for certifying that V is not a tile. The first involves impossibility of a bin-packing problem, and the second involves infeasibility of a linear program. We apply both criteria to a list of putative tiles given by Gordon, Miller, and Ostapenko in that none of them are, in fact, tiles.

Affiliated with

Also associated with

No associations

Rating

Binary Non-tiles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Binary Non-tiles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary Non-tiles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699400