Abstract
In 1986, Kreher and Radziszowski were the first who used the famous LLL algorithm to construct combinatorial designs. Subsequently, lattice algorithms have been applied to construct a large variety of objects in design theory, coding theory and finite geometry. Unfortunately, the use of lattice algorithms in combinatorial search is still not well established. Here, we provide a list of problems which could be tackled with this approach and give an overview on exhaustive search using lattice basis reduction. Finally, we describe a different enumeration strategy which might improve the power of this method even further.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Updated versions available at https://www-cs-faculty.stanford.edu/~knuth/programs.html.
References
Aardal, K., Hurkens, C., Lenstra, A.K.: Solving a linear diophantine equation with lower and upper bounds on the variables. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 229–242. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69346-7_18
Betten, A., Kerber, A., Laue, R., Wassermann, A.: Simple 8-designs with small parameters. Des. Codes Crypt. 15, 5–27 (1998)
Betten, A., Kerber, A., Kohnert, A., Laue, R., Wassermann, A.: The discovery of simple 7-designs with automorphism group \(P{\Gamma }L\)(2, 32). In: Cohen, G., Giusti, M., Mora, T. (eds.) AAECC 1995. LNCS, vol. 948, pp. 131–145. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60114-7_10
Betten, A., Klin, M., Laue, R., Wassermann, A.: Graphical \(t\)-designs. Discrete Math. 197(198), 111–121 (1999)
Betten, A., Laue, R., Wassermann, A.: New \(t\)-designs and large sets of \(t\)-designs. Discrete Math. 197(198), 83–109 (1999)
Bouyukliev, I., Bouyuklieva, S., Kurz, S.: Computer classification of linear codes. CoRR abs/2002.07826 (2020). https://arxiv.org/abs/2002.07826
Braun, M., Kohnert, A., Wassermann, A.: Construction of \((n, r)\)-arcs in PG(\(2, q\)). Innovations Incidence Geom. 1, 133–141 (2005)
Braun, M., Kerber, A., Laue, R.: Systematic construction of \(q\)-analogs of \(t\)-\((v, k,\lambda )\)-designs. Des. Codes Crypt. 34(1), 55–70 (2005). https://doi.org/10.1007/s10623-003-4194-z
Braun, M., Kiermaier, M., Kohnert, A., Laue, R.: Large sets of subspace designs. J. Comb. Theory Ser. A 147, 155–185 (2017). https://doi.org/10.1016/j.jcta.2016.11.004
Braun, M., Kiermaier, M., Wassermann, A.: Computational methods in subspace designs. In: Greferath, M., Pavčević, M.O., Silberstein, N., Vázquez-Castro, M.Á. (eds.) Network Coding and Subspace Designs. SCT, pp. 213–244. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-70293-3_9
Braun, M., Kohnert, A., Östergård, P.R.J., Wassermann, A.: Large sets of \(t\)-designs over finite fields. J. Comb. Theory A 124, 195–202 (2014)
Braun, M., Kohnert, A., Wassermann, A.: Optimal linear codes from matrix groups. IEEE Trans. Inform. Theory 51(12), 4247–4251 (2005). https://doi.org/10.1109/TIT.2005.859291
Buratti, M., Kiermaier, M., Kurz, S., Nakić, A., Wassermann, A.: \(q\)-analogs of group divisible designs. In: Pseudorandomness and Finite Fields, Radon Series on Computational and Applied Mathematics, vol. 23. DeGruyter (2019)
Buratti, M., Wassermann, A.: On decomposability of cyclic triple systems. Australas. J. Comb. 71(2), 184–195 (2018)
Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer, Berlin (1993). https://doi.org/10.1007/978-3-662-02945-9
Colbourn, C.J., Dinitz, J.H.: Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, Boca Raton (2006)
Coster, M., Joux, A., LaMacchia, B., Odlyzko, A., Schnorr, C., Stern, J.: Improved low-density subset sum algorithms. Comput. Complex. 2, 111–128 (1992)
Coster, M.J., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.P.: An improved low-density subset sum algorithm. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 54–67. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_4
Coveyou, R., MacPherson, R.: Fourier analysis of uniform random number generators. J. ACM 14, 100–119 (1967)
Dieter, U.: How to calculate shortest vectors in a lattice. Math. Comput. 29(131), 827–833 (1975)
Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44, 463–471 (1985)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Gibbons, P.B., Östergård, P.R.J.: Computational methods in design theory. In: Colbourn, C.J., Dinitz, J.H. (eds.) Handbook of Combinatorial Designs, chap. VII.6, 2 edn, pp. 755–783. Chapman & Hall/CRC, Boca Raton (2007)
Gurobi Optimization: Gurobi optimizer reference manual (2016). http://www.gurobi.com
Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995, vol. 1. pp. 607–613. Morgan Kaufmann Publishers Inc., San Francisco (1995)
Hermite, C.: Extraits de lettres de M.Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres. J. reine angew. Math. 40, 279–290 (1850)
IBM: ILOG CPLEX Optimizer (2010)
Kaib, M., Ritter, H.: Block reduction for arbitrary norms. Preprint, Universität Frankfurt (1995)
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)
Karoui, W., Huguet, M.-J., Lopez, P., Naanaa, W.: YIELDS: a yet improved limited discrepancy search for CSPs. In: Van Hentenryck, P., Wolsey, L. (eds.) CPAIOR 2007. LNCS, vol. 4510, pp. 99–111. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72397-4_8
Kaski, P., Östergård, P.R.: Classification Algorithms for Codes and Designs. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-28991-7
Kiermaier, M., Kurz, S., Solé, P., Stoll, M., Wassermann, A.: On strongly walk regular graphs, triple sum sets and their codes. ArXiv e-prints, abs/1502.02711 (2020)
Kiermaier, M., Laue, R., Wassermann, A.: A new series of large sets of subspace designs over the binary field. Des. Codes Crypt. 86(2), 251–268 (2018). https://doi.org/10.1007/s10623-017-0349-1
Kiermaier, M., Wassermann, A., Zwanzger, J.: New upper bounds on binary linear codes and a \({\mathbb{Z}}_{4}\)-code with a better-than-linear Gray image. IEEE Trans. Inf. Theory 62(12), 6768–6771 (2016). https://doi.org/10.1109/TIT.2016.2612654
Knuth, D.E.: Dancing links. In: Davies, J., Roscoe, B., Woodcock, J. (eds.) Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare. Palgrave (2000)
Knuth, D.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading (1969)
Kohnert, A.: Constructing two-weight codes with prescribed groups of automorphisms. Discret. Appl. Math. 155(11), 1451–1457 (2007). https://doi.org/10.1016/j.dam.2007.03.006
Korkine, A., Zolotareff, G.: Sur les formes quadratiques. Math. Ann. 6, 366–389 (1873)
Kramer, E.S., Mesner, D.M.: \(t\)-designs on hypergraphs. Discret. Math. 15(3), 263–296 (1976). https://doi.org/10.1016/0012-365X(76)90030-3
Kreher, D.L., Radziszowski, S.P.: The existence of simple \(6\)-\((14,7,4)\) designs. J. Comb. Theory Ser. A 43, 237–243 (1986)
Kreher, D.L., Radziszowski, S.P.: Finding simple \(t\)-designs by using basis reduction. Congr. Numer. 55, 235–244 (1986)
Krčadinac, V.: Some new designs with prescribed automorphism groups. J. Comb. Des. 26(4), 193–200 (2018). https://doi.org/10.1002/jcd.21587
Krčadinac, V., Pavčević, M.O.: New small 4-designs with nonabelian automorphism groups. In: Blömer, J., Kotsireas, I.S., Kutsia, T., Simos, D.E. (eds.) MACIS 2017. LNCS, vol. 10693, pp. 289–294. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72453-9_23
Lagarias, J., Odlyzko, A.: Solving low-density subset sum problems. J. Assoc. Comp. Mach. 32, 229–246 (1985). Appeared already in Proceedings of 24th IEEE Symposium on Foundations of Computer Science, pp. 1–10 (1983)
Laue, R.: Constructing objects up to isomorphism, simple 9-designs with small parameters. In: Betten, A., Kohnert, A., Laue, R., Wassermann, A. (eds.) Algebraic Combinatorics and Applications, pp. 232–260. Springer, Heidelberg (2001). https://doi.org/10.1007/978-3-642-59448-9_16
Laue, R., Magliveras, S., Wassermann, A.: New large sets of t-designs. J. Comb. Des. 9, 40–59 (2001)
Laue, R., Omidi, G.R., Tayfeh-Rezaie, B., Wassermann, A.: New large sets of \(t\)-designs with prescribed groups of automorphisms. J. Combin. Des. 15(3), 210–220 (2007). https://doi.org/10.1002/jcd.20128
Lenstra, A., Lenstra Jr., H., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
Mathon, R.: Computational methods in design theory. In: Keedwell, A.D. (ed.) Surveys in Combinatorics, Proc. 13th Br. Comb. Conf., Guildford/UK 1991, vol. 166, pp. 101–117. London Mathematical Society Lecture Note (1991)
Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems. Kluwer Academic Publishers (2002)
Minkowski, H.: Geometrie der Zahlen. Teubner, Leipzig (1896)
Nguyen, P.Q., Vallée, B.: The LLL Algorithm: Survey and Applications, 1st edn. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02295-1
Niskanen, S., Östergård, P.R.J.: Cliquer user’s guide, version 1.0. Technical report T48, Helsinki University of Technology (2003)
Östergård, P.R.J., Quistorff, J., Wassermann, A.: New results on codes with covering radius 1 and minimum distance 2. Des. Codes Crypt. 35, 241–250 (2005)
Ritter, H.: Aufzählung von kurzen Gittervektoren in allgemeiner Norm. Ph.D. thesis, Universität Frankfurt (1997)
Schnorr, C.: A hierachy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 201–224 (1987)
Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. In: Budach, L. (ed.) FCT 1991. LNCS, vol. 529, pp. 68–85. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54458-5_51
Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-49264-X_1
van Beek, P.: Backtracking search algorithms. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, pp. 85–134. Elsevier (2006). https://doi.org/10.1016/S1574-6526(06)80008-8
Wassermann, A.: Finding simple \(t\)-designs with enumeration techniques. J. Comb. Des. 6(2), 79–90 (1998)
Wassermann, A.: Attacking the market split problem with lattice point enumeration. J. Comb. Optim. 6, 5–16 (2002)
Wassermann, A.: Computing the minimum distance of linear codes. In: Eighth International Workshop Algebraic and Combinatorial Coding Theory (ACCT VIII), Tsarskoe Selo, Russia, pp. 254–257 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Wassermann, A. (2021). Search for Combinatorial Objects Using Lattice Algorithms – Revisited. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms. IWOCA 2021. Lecture Notes in Computer Science(), vol 12757. Springer, Cham. https://doi.org/10.1007/978-3-030-79987-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-79987-8_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79986-1
Online ISBN: 978-3-030-79987-8
eBook Packages: Computer ScienceComputer Science (R0)