1. Home
  2. Issues
  3. Volume 35, Issue 1 (2024)
  4. Shadow Minimization Boolean Function Rec ...

Informatica


Shadow Minimization Boolean Function Reconstruction
Volume 35, Issue 1 (2024), pp. 1–20
Pub. online: 14 February 2024      Type: Research Article      Open accessOpen Access
Received
1 November 2023
Accepted
1 February 2024
Published
14 February 2024

Abstract

A special class of monotone Boolean functions coming from shadow minimization theory of finite set-systems – KK-MBF functions – is considered. These functions are a descriptive model for systems of compatible groups of constraints, however, the class of all functions is unambiguously complex and it is sensible to study relatively simple subclasses of functions such as KK-MBF. Zeros of KK-MBF functions correspond to initial segments of lexicographic order on hypercube layers. This property is used to simplify the recognition. Lexicographic order applies priorities over constraints which is applicable property of practices. Query-based algorithms for KK-MBF functions are investigated in terms of their complexities.

References

 
Aslanyan, L.H. (1979). The discrete isoperimetry problem and related extremal problems for discrete spaces. Problemy Kibernetiki, 36, 85–128.
 
Aslanyan, L., Sahakyan, H. (2009). Chain split and computations in practical rule mining. In: Intenational Book Series Information Science and Computing, Book 8, Classification, Forecasting, Data Mining. Institute of Information Theories and Applications, FOI ITHEA, Bulgaria, pp. 132–135.
 
Aslanyan, L., Sahakyan, H. (2017). The splitting technique in monotone recognition. Discrete Applied Mathematics, 216, 502–512.
 
Aslanyan, L., Sahakyan, H., Romanov, V., Da Costa, G., Kacimi, R. (2019). Large network target coverage protocols. In: 2019 Computer Science and Information Technologies (CSIT), Yerevan, Armenia, 2019, pp. 57–64. https://doi.org/10.1109/CSITechnol.2019.8895058.
 
Aslanyan, L., Gishyan, K., Sahakyan, H. (2023a). Target class classification recursion preliminaries. Baltic Journal of Modern Computing, 11(3), 398–410.
 
Aslanyan, L., Katona, G., Sahakyan, H. (2023b). Notes on reconstruction of shadow minimization Boolean functions. In: 2023 Computer Science and Information Technologies (CSIT), Yerevan, Armenia, 2023, September 25–30, pp. 119–123.
 
Balogh, J., Katona, G.O., Linz, W., Tuza, Z. (2021). The domination number of the graph defined by two levels of the n-cube, II. European Journal of Combinatorics, 91, 103201.
 
Bezrukov, S., Kuzmanovski, N., Lim, J. (2023). Pull-push method: a new approach to edge-isoperimetric problems. Discrete Mathematics, 346(12), 113632.
 
BFA (2023). Ninth Dedekind number discovered: scientists solve long-known problem in mathematics. In: The 8th International Workshop on Boolean Functions and their Applications (BFA), in memory of Kai-Uwe Schmidt, September 3–8, 2023, Voss, Norway.
 
Black, H., Chakrabarty, D., Seshadhri, C. (2023). Directed isoperimetric theorems for Boolean functions on the hypergrid and an $O(n\sqrt{d})$ monotonicity tester. In: STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 233–241.
 
Blum, A. (2003). Learning a function of r relevant variables. In: Learning Theory and Kernel Machines, 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT, Kernel 2003, Washington, DC, USA, August 24–27, 2003. Springer, Berlin, Heidelberg, pp. 731–733.
 
Boros, E., Hammer, P. (2002). Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225.
 
Boros, E., Hammer, P., Ibaraki, T., Kawakami, K. (1991). Identifying 2-monotonic positive Boolean functions in polynomial time. In: ISA’91 Algorithms: 2nd International Symposium on Algorithms Taipei, Republic of China, December 16–18, 1991. Springer, Berlin, Heidelberg, pp. 104–115.
 
Braverman, M., Khot, S., Kindler, G., Minzer, D. (2022). Improved monotonicity testers via hypercube embeddings. Preprint: arXiv:2211.09229v1.
 
Carlet, C., Joyner, D., Stănică, P., Tang, D. (2016). Cryptographic properties of monotone Boolean functions. Journal of Mathematical Cryptology, 10(1), 1–14.
 
Chao, T.-W., Yu, H.-H.H. (2023). Kruskal–Katona-type problems via entropy method. Preprint: arXiv:2307.15379.
 
Clements, G.F. (1973). A minimization problem concerning subsets of a finite set. Discrete Mathematics, 4(2), 123–128.
 
Crawford-Kahrl, P., Cummins, B., Gedeon, T. (2022). Joint realizability of monotone Boolean functions. Theoretical Computer Science, 922, 447–474.
 
Damásdi, G., Gerbner, D., Katona, G.O., Keszegh, B., Lenger, D., Methuku, A., Nagy, D.T., Pálvölgyi, D., Patkós, B., Vizer, M., Wiener, G., (2021). Adaptive majority problems for restricted query graphs and for weighted sets. Discrete Applied Mathematics, 288, 235–245.
 
Daykin, D.E., Godfrey, J., Hilton, A.J.W. (1974). Existence theorems for Sperner families. Journal of Combinatorial Theory, Series A, 17(2), 245–251.
 
Dedekind, R. (1895). Uber die Begründung der Idealtheorie. Gött. Nachr, 106–113.
 
Frankl, P., Katona, G.O. (2021). On strengthenings of the intersecting shadow theorem. Journal of Combinatorial Theory, Series A, 184, 105510.
 
Freixas, J. (2022). On the enumeration of some inequivalent monotone Boolean functions. Optimization, https://doi.org/10.1080/02331934.2022.2154126.
 
Gainanov, D.N. (1984). On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 24(8), 1250–1257.
 
Griggs, J.R., Kalinowski, T., Leck, U., Roberts, I.T., Schmitz, M. (2023). The saturation spectrum for antichains of subsets. Order, 40, 537–574. https://doi.org/10.1007/s11083-022-09622-6.
 
Hansel, G. (1966). Sur le nombre des fonctions Booléennes monotones de n variables. Comptes Rendus de l’Académie des Sciences, 262(20), 1088–1090.
 
Jackson, J.C., Lee, H.K., Servedio, R.A., Wan, A. (2011). Learning random monotone DNF. Discrete Applied Mathematics, 159(5), 259–271.
 
Jung, A. (2023). Shadow ratio of hypergraphs with bounded degree. Graphs and Combinatorics, 39(3), 40.
 
Kabulov, A., Berdimurodov, M. (2021). Parametric algorithm for searching the minimum lower unity of monotone Boolean functions in the process synthesis of control automates. In: 2021 International Conference on Information Science and Communications Technologies (ICISCT), Tashkent, Uzbekistan, 2021, pp. 1–4. https://doi.org/10.1109/ICISCT52966.2021.9670370.
 
Katona, G. (1968). A theorem of finite sets. In: Theory of Graphs (Proceedings of the Colloquim held at Tihany). Academic Press, New York.
 
Katona, G. (1987). A theorem of finite sets. In: Classic Papers in Combinatorics, pp. 381–401.
 
Korobkov, V.K. (1965). On monotone functions of the algebra of logic. Problemy Kibernetiki, 13, 5–28.
 
Korshunov, A.D. (1981). On the number of monotone Boolean menge. Problemy Kibernetiki, 38, 5–109.
 
Korshunov, A.D. (2003). Monotone Boolean functions. Russian Mathematical Surveys, 58(5), 929.
 
Kovalerchuk, B., Delizy, F. (2005). Visual data mining using monotone Boolean functions. In: Visual and Spatial Analysis: Advances in Data Mining, Reasoning, and Problem Solving. Springer, Dordrecht, pp. 387–406.
 
Kruskal, J.B. (1963). The number of simplices in a complex. Mathematical Optimization Techniques, 10, 251–278.
 
Kulhandjian, M., Aslanyan, L., Sahakyan, H., Kulhandjian, H., D’Amours, C. (2019). Multidisciplinary discussion on 5G from the viewpoint of algebraic combinatorics. In: 2019 Computer Science and Information Technologies (CSIT), Yerevan, Armenia, 2019, pp. 69–76, https://doi.org/10.1109/CSITechnol.2019.8895166.
 
Lange, J., Vasilyan, A. (2023). Agnostic proper learning of monotone functions: beyond the black-box correction barrier. Preprint: arXiv:2304.02700.
 
Lovász, L. (2007). Combinatorial Problems and Exercises, 3nd edition. American Mathematical Society.
 
Madden, G.N. (2023). Shadows of Colored Complexes and Cycle Decompositions of Equipartite Hypergraphs. PhD thesis, Illinois State University.
 
Nosov, M.V. (2023). Estimates of the degrees of separating polynomials for monotone and self-dual functions. Intelligent Systems. Theory and Applications, 27(2), 79–82.
 
O’Donnell, R., Servedio, R. (2005). Learning monotone functions from random examples in polynomial time. CMU School of Computer Science. Citeseer.
 
Sahakyan, H. (2013). (0, 1)-matrices with different rows. In: Ninth International Conference on Computer Science and Information Technologies Revised Selected Papers, Yerevan, Armenia, 2013, pp. 1–7. https://doi.org/10.1109/CSITechnol.2013.6710342.
 
Sahakyan, H. (2015). On the set of simple hypergraph degree sequences. Applied Mathematical Sciences, 9(5), 243–253.
 
Sahakyan, H. (2023). On nonconvexity of the set of hypergraphic sequences. In: 2023 Computer Science and Information Technologies (CSIT). NAS RA, pp. 47–52.
 
Sahakyan, H., Aslanyan, L. (2017). Discrete tomography with distinct rows: relaxation. In: 2017 Computer Science and Information Technologies (CSIT). Yerevan, Armenia, 2017, pp. 117–120. https://doi.org/10.1109/CSITechnol.2017.8312153.
 
Sahakyan, H., Aslanyan, L., Katona, G. (2022). Notes on identification of monotone Boolean functions with machine learning methods. In: Proceedings of “Middle-European Conference on Applied Theoretical Computer Science” Conference. Koper, Slovenia, 13–14 October 2022.
 
Sales, M., Schülke, B. (2022). A local version of Katona’s intersection theorem. Preprint: arXiv:2206.04278.
 
Schröder, B. (2016). Ordered Sets: An Introduction with Connections from Combinatorics to Topology. Birkhäuser.
 
Sokolov, N.A. (1987). Optimal reconstruction of monotone Boolean functions. Computational Mathematics and Mathematical Physics, 27(6), 181–187.
 
Tennakoon, R., Suter, D., Zhang, E., Chin, T.-J., Bab-Hadiashar, A. (2021). Consensus maximisation using influences of monotone Boolean functions. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2866–2875.
 
Tonoyan, G.P. (1979). Chain partitioning of n-cube vertices and deciphering of monotone Boolean functions. Journal of Computational Mathematics and Mathematical Physics, 19(6), 1532–1542.
 
Valiant, L.G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134–1142.
 
Zhang, E., Suter, D., Tennakoon, R., Chin, T.-J., Bab-Hadiashar, A., Truong, G., Gilani, S.Z. (2022). Maximum consensus by weighted influences of monotone Boolean functions. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, New Orleans, LA, USA, 2022, pp. 8964–8972. https://doi.org/10.1109/CVPR52688.2022.00876.
 
Zhuravlev, Y.I., Ryazanov, V.V., Aslanyan, L.H., Sahakyan, H.A. (2019). On a classification method for a large number of classes. Pattern Recognition and Image Analysis, 29, 366–376.
 
Zhuravlev, Y.I., Ryazanov, V.V., Ryazanov, V.V., Aslanyan, L.H., Sahakyan, H.A. (2020). Comparison of different dichotomous classification algorithms. Pattern Recognition and Image Analysis, 30, 303–314.

Biographies

Aslanyan Levon
https://orcid.org/0000-0002-5354-2730
lasl@sci.am

L. Aslanyan graduated from Novosibirsk State University in 1968. He received his PhD in 1976, and his doctorate in 1997. He is a professor since 1997 and a corresponding member of National Academy of Sciences of the Republic of Armenia since 2014. He currently heads the Department of Discrete Modelling, Analysis, and Recognition at the Institute for Informatics and Automation Problems of the NAS RA. Research interests: mathematical logic, discrete mathematics, mathematical theory of pattern recognition and artificial intelligence.

Katona Gyula
https://orcid.org/0000-0002-0188-0391
katona.gyula.oh@renyi.hu

G. Katona, prof., is a doctor of the mathematical sciences. He is an academician of the Hungarian Academy of Sciences, a member of the European Academy of Sciences, a foreign member of the Bulgarian Academy of Sciences, a research professor at Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, and a professor at the Eötvös L. University. His main research areas include extreme combinatorial aanalysis.

Sahakyan Hasmik
https://orcid.org/0000-0002-8449-6845
hsahakyan@sci.am

H. Sahakyan graduated from Yerevan State University. She received her PhD in 2002 and her doctorate in 2018. She is currently a scientific secretary of the Institute for Informatics and Automation Problems of the NAS RA and a leading researcher at the Discrete Mathematics Department. Scientific interests: combinatorics, discrete optimization, discrete tomography, artificial intelligence, and data mining.


Full article PDF XML
Full article PDF XML

Copyright
© 2024 Vilnius University
Open access article under the CC BY license.

Keywords
monotone Boolean function reconstruction lexicographic order shadow KK-MBF class

Metrics
since January 2020
493

Article info
views

176

Full article
views

211

PDF
downloads

59

XML
downloads


Share


RSS