Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael Saks, and Navid Talebanfard. Local Enumeration and Majority Lower Bounds. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gurumukhani_et_al:LIPIcs.CCC.2024.17, author = {Gurumukhani, Mohit and Paturi, Ramamohan and Pudl\'{a}k, Pavel and Saks, Michael and Talebanfard, Navid}, title = {{Local Enumeration and Majority Lower Bounds}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {17:1--17:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.17}, URN = {urn:nbn:de:0030-drops-204136}, doi = {10.4230/LIPIcs.CCC.2024.17}, annote = {Keywords: Depth 3 circuits, k-CNF satisfiability, Circuit lower bounds, Majority function} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Kazuyuki Amano. Depth-Three Circuits for Inner Product and Majority Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{amano:LIPIcs.ISAAC.2023.7, author = {Amano, Kazuyuki}, title = {{Depth-Three Circuits for Inner Product and Majority Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.7}, URN = {urn:nbn:de:0030-drops-193092}, doi = {10.4230/LIPIcs.ISAAC.2023.7}, annote = {Keywords: Circuit complexity, depth-3 circuits, upper bounds, lower bounds, computer-assisted proof} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kazuyuki Amano. Integer Complexity and Mixed Binary-Ternary Representation. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{amano:LIPIcs.ISAAC.2022.29, author = {Amano, Kazuyuki}, title = {{Integer Complexity and Mixed Binary-Ternary Representation}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.29}, URN = {urn:nbn:de:0030-drops-173146}, doi = {10.4230/LIPIcs.ISAAC.2022.29}, annote = {Keywords: Integer complexity, Lower bounds, Upper bounds, Horner’s schema, Computer assisted proof} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Kazuyuki Amano. Depth Two Majority Circuits for Majority and List Expanders. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{amano:LIPIcs.MFCS.2018.81, author = {Amano, Kazuyuki}, title = {{Depth Two Majority Circuits for Majority and List Expanders}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {81:1--81:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.81}, URN = {urn:nbn:de:0030-drops-96633}, doi = {10.4230/LIPIcs.MFCS.2018.81}, annote = {Keywords: Boolean function, majority function, constant depth circuit, expander graph} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Kazuyuki Amano and Yoshinobu Haruyama. On the Number of p4-Tilings by an n-Omino. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{amano_et_al:LIPIcs.ISAAC.2017.5, author = {Amano, Kazuyuki and Haruyama, Yoshinobu}, title = {{On the Number of p4-Tilings by an n-Omino}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {5:1--5:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.5}, URN = {urn:nbn:de:0030-drops-82498}, doi = {10.4230/LIPIcs.ISAAC.2017.5}, annote = {Keywords: polyomino, plane tiling, isohedral tiling, word factorization} }