HomeIssuesOne-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes

One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/2

The fact of a one-to-one correspondence between regular families of Boolean functions and edge orientations with a unique sink on Boolean cubes is proved. This correspondence allows us to transfer some of the results obtained for the indicated orientations to the language of regular families: to obtain estimates for the number of regular families of length n ≥ 5 and to show that the problem of recognizing the correctness of a family is coNP-complete.
Download file
Counter downloads: 98
  • Title One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
  • Headline One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 48
  • Date:
  • DOI 10.17223/20710410/48/2
Keywords
правильные семейства булевых функций, рёберные ориентации с единственным стоком, proper families of Boolean functions, unique sink orientations
Authors
References
Keedwell A. and Denes J. Latin Squares and their Applications, 2nd Ed. North Holland, 2015. 438 p.
Глухов М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. 2008. №2(2). С. 28-32.
Носов В. А. Построение классов латинских квадратов в булевой базе данных // Интеллектуальные системы. 1999. Т. 4. Вып. 3-4. C. 307-320.
Носов В. А. Построение параметрического семейства латинских квадратов в векторной базе данных // Интеллектуальные системы. 2006. Т. 8. Вып. 1-4. С. 517-529.
Szabo T. and Welzl E. Unique sink orientations of cubes // Proc. 42nd IEEE Symp. FOCS. Newport Beach, CA, USA, 2001. P.547-555.
Schurr I. Unique Sink Orientations of Cubes. Doctoral Thesis. ETH Zurich, 2004.
Носов В. А., Панкратьев А. Е. О функциональном задании латинских квадратов // Интеллектуальные системы. 2008. Т. 12. Вып. 1-4. С. 317-332.
Gartner B. and Thomas A. The complexity of recognizing unique sink orientations // Leibniz Intern. Proc. Informatics (LIPIcs). 2015. V. 30. P.341-353.
Matousek J. The number of unique-sink orientations of the hypercube // Combinatorica. 2006. V. 26. P. 91-99.
One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/2
One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/2