Circuit Complexity

References

Publications: 

• 2023: M. Sönmez Turan. Optimizing implementations of Boolean Functions. 8th International Workshop on Boolean Functions and their Applications (BFA). Also at ia.cr/2024/133
• 2022: M. Sönmez Turan. New Bounds on the Multiplicative Complexity of Boolean Functions. 7th International Workshop on Boolean Functions and their Applications (BFA). Also at ia.cr/2022/1077
• 2021: M. Sönmez Turan, and R. Peralta, On the Multiplicative Complexity of Cubic Boolean Functions. https://ia.cr/2021/1041
• 2020: Çalık, Ç., Turan, M.S. & Peralta, R. Boolean functions with multiplicative complexity 3 and 4. Cryptogr. Commun. 12, 935–946 (2020). DOI: 10.1007/s12095-020-00445-z. Also at ia.cr/2019/1364
• 2019: Ç. Çalık, M. Dworkin, N. Dykas, and R. Peralta. Searching for Best Karatsuba Recurrences. Analysis of Experimental Algorithms (SEA 2019), LNCS vol. 11544, pp 332-342, Springer International Publishing, 2019. DOI: 10.1007/978-3-030-34029-2_22. Preprint available at NIST.
• 2019: L.T.A.N. Brandão, Ç. Çalık, M. Sönmez Turan, and R. Peralta. Upper bounds on the multiplicative complexity of symmetric Boolean functions. Cryptography and Communications, vol. 11, pp. 1339–1362 (2019). DOI: 10.1007/s12095-019-00377-3. Also at ia.cr/2019/708
• 2018: Ç. Çalık, M. Sönmez Turan, and R. Peralta, The multiplicative complexity of 6-variable Boolean functions. Cryptography and Communications. Special Issue on Boolean Functions and Their Applications, pp. 1–15, 2018. doi:10.1007/s12095-018-0297-2. Also at ia.cr/2018/002
• 2018: A. Visconti, C.V. Schiavo, R. Peralta. Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2). Information Processing Letters. Vol. 137, Sep. 2018, Pages 1-5. doi:10.1016/j.ipl.2018.04.010. Copy available at NIH.
• 2017: M. Gausdal Find, Daniel Smith-Tone, M. Sönmez Turan. The number of boolean functions with multiplicative complexity 2. IJICoT 4(4): 222-236 (2017). doi:10.5555/3150183.3150185. Also at ia.cr/2015/1041
• 2016: M. Gausdal Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Foundations of Computer Science, FOCS 2016. doi:10.1109/FOCS.2016.19
• 2014: M. Sönmez Turan and R. Peralta, The Multiplicative Complexity of Boolean Functions on Four and Five Variables. In Proc. 3rd International Workshop on Lightweight Cryptography for Security and Privacy — LightSec 2014(T. Eisenbarth and E. Öztürk, eds.), vol. 8898 of LNCS, pp. 21–33, Springer, 2015. doi:10.1007/978-3-319-16363-5_2. Also at ia.cr/2015/848
• 2013: J. Boyar, P. Matthews, and R. Peralta. Logic Minimization Techniques with Applications to Cryptology. Journal of Cryptology, vol. 26, pp. 280–312 (2013). doi:10.1007/s00145-012-9124-7
• 2008: J. Boyar and R. Peralta, Tight bounds for the multiplicative complexity of symmetric functions. Theoretical Computer Science, vol. 396, no. 1-3, pp. 223–246, 2008. doi:10.1016/j.tcs.2008.01.030. Copy available at NIST.
• 2000: J. Boyar, R. Peralta, and D. Pochuev, On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1). Theoretical Computer Science, vol. 235, no. 1, pp. 43 – 57, 2000. doi:10.1016/S0304-3975(99)00182-6 

Other links: 

• Circuit complexity team at the Cryptographic Technology Group, NIST. Circuits for functions of interest to cryptography. GitHub:usnistgov/Circuits, 2019.