Updated on 2026/05/29

写真a

 
UCHIZAWA Kei
 
Title
Associate Professor

Research Areas

  • Informatics / Theory of informatics

 

Papers

  • On Saving Energy in Boolean Circuits via Negations, Fundamentals of Computation Theory. FCT 2025. Lecture Notes in Computer Science, 16106 , 2025.09

    Jayalal Sarma, Kei Uchizawa

    Multiple Authorship (Including Foreigners)

  • Trade-Offs Between Energy and Depth of Neural Networks, NEURAL COMPUTATION, 36(8) 1541-1567, 2024.07

    Uchizawa, K; Abe, H

    Single Author

  • Energy and Output Patterns in Boolean Circuits, Theory and Applications of Models of Computation. TAMC 2024. Lecture Notes in Computer Science, 14637 , 2024.05

    Jayalal Sarma, Kei Uchizawa

    Multiple Authorship (Including Foreigners)

  • Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions, THEORY OF COMPUTING SYSTEMS, 67(3) 569-591, 2023.06

    Ogihara, M; Uchizawa, K

    Multiple Authorship (Including Foreigners)

  • Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy, Proceedings of 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), - , 2023

    内沢 啓

    Single Author

  • An <i>O</i>(<i>n</i><sup>2</sup>)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position, IEICE Transactions on Information and Systems, E105D(3) 503-507, 2022.03

    KOBAYASHI Yasuaki, NAKANO Shin-ichi, UCHIZAWA Kei, UNO Takeaki, YAMAGUCHI Yutaro, YAMANAKA Katsuhisa

    Single Author

  • FOREWORD, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 104(9) 1093, 2021

    UCHIZAWA Kei

    Single Author

  • Size, Depth and Energy of Threshold Circuits Computing Parity Function, Proc of 31st International Symposium on Algorithms and Computation, 2020

    Kei Uchizawa

    Single Author

  • Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions, Proc. of 45th International Symposium on Mathematical Foundations of Computer Science, 2020

    Mitsunori Ogihara and Kei Uchizawa

    Multiple Authorship (Including Foreigners)

  • Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions, Proceedings of 45th International Symposium on Mathematical Foundations of Computer Science, 170 , 2020

    内沢 啓

    Single Author

  • Size, Depth and Energy of Threshold Circuits Computing Parity Function, Proceedings of 31st International Symposium on Algorithms and Computation, 181 , 2020

    内沢 啓

    Single Author

  • Energy and Depth of Threshold Circuits Computing Parity Function (Recent Trends in Algorithms and Computation), 数理解析研究所講究録, 2132 20-22, 2019.10

    内澤 啓

    Single Author

  • Computational Power of Threshold Circuits of Energy at most Two, {IEICE} Transactions, 101-A(9) 1431, 2018

    Hiroki Maniwa and Takayuki Oki and Akira Suzuki and Kei Uchizawa and Xiao Zhou

    Multiple Authorship (Including Foreigners)

  • Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, INFORMATION AND COMPUTATION, 256 226-236, 2017.10

    Ogihara, M; Uchizawa, K

    Multiple Authorship (Only Japanese)

  • Generalized predecessor existence problems for Boolean, 42nd {I}nternational {S}ymposium on {M}athematical, 83 Art. No. 8, 13, 2017

    Kawachi, Akinori, Ogihara, Mitsunori, Uchizawa, Kei

    Multiple Authorship (Including Foreigners)

  • Hitori Numbers, Journal of Information Processing, 25 695-707, 2017

    Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

    Multiple Authorship (Only Japanese)

  • Threshold Circuits Detecting Global Patterns in Two-dimensional Maps, Journal of Graph Algorithms and Applications, 20(1) 115, 2016

    Uchizawa, Kei and Yashima, Daiki, Zhou, Xiao

    Multiple Authorship (Only Japanese)

  • Swapping labeled tokens on graphs, Theoretical Computer Science, 586 81-94, 2015.06

    Yamanaka, Katsuhisa, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Un

    Multiple Authorship (Including Foreigners)

  • Swapping labeled tokens on graphs, THEORETICAL COMPUTER SCIENCE, 586 81-94, 2015.06

    Yamanaka, K; Demaine, ED; Ito, T; Kawahara, J; Kiyomi, M; Okamoto, Y; Saitoh, T; Suzuki, A; Uchizawa, K; Uno, T

    Multiple Authorship (Only Japanese)

  • Competitive Diffusion on Weighted Graphs, Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science, 9214 422-433, 2015

    Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

    Multiple Authorship (Including Foreigners)

  • Lower bounds for linear decision trees with bounded weights, Theory and Practice of Computer Science. SOFSEM 2015. Lecture Notes in Computer Science, 8939 412-422, 2015

    Uchizawa Kei, Takimoto Eiji

    Multiple Authorship (Only Japanese)

  • Threshold circuits for global patterns in 2-dimensional maps, WALCOM: Algorithms and Computation. WALCOM 2015. Lecture Notes in Computer Science, 8973 306-316, 2015

    Uchizawa Kei, Yashima Daiki, Zhou, Xiao

    Multiple Authorship (Only Japanese)

  • Generalized rainbow connectivity of graphs, THEORETICAL COMPUTER SCIENCE, 555 35-42, 2014.10

    Uchizawa, K; Aoki, T; Ito, T; Zhou, X

    Multiple Authorship (Only Japanese)

  • Swapping labeled tokens on graphs, Fun with Algorithms. FUN 2014. Lecture Notes in Computer Science, 8496 364-375, 2014

    Yamanaka Katsuhisa, Demaine Erik D., Ito Takehiro, Kawahara Jun, Kiyomi Masashi, Okamoto Yoshio, Saitoh Toshiki, Suzuki Akira, Uchizawa Kei, Uno Takeaki

    Multiple Authorship (Including Foreigners)

  • Lower bounds for threshold circuits of bounded energy, Interdisciplinary Information Sciences, 20(1) 27-50, 2014

    Kei Uchizawa

    Single Author

  • On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms, Algorithmica, 67(2) 161-179, 2013.09

    Uchizawa Kei , Aoki, Takanori, Ito Takehiro, Suzuki Akira

    Multiple Authorship (Including Foreigners)

  • Energy and fan-in of logic circuits computing symmetric Boolean functions, Theoretical Computer Science, 505 74-80, 2013

    Suzuki Akira and Uchizawa Kei and Zhou Xiao

    Multiple Authorship (Including Foreigners)

  • Energy-efficient threshold circuits computing MOD functions, International Journal of Foundations of Computer Science, 24(1) 15-29, 2013

    Suzuki Akira, Uchizawa Kei, Zhou Xiao

    Multiple Authorship (Including Foreigners)

  • Generalized rainbow connectivity of graphs, Algorithms and Computation. WALCOM 2013. Lecture Notes in Computer Science, 7748 233-244, 2013

    Uchizawa Kei, Aoki Takanori, Ito Takehiro, Zhou Xiao

    Multiple Authorship (Including Foreigners)

  • Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimentional Arrays, Theory and Applications of Models of Computation. TAMC 2013. Lecture Notes in Computer Science, 7876 248-259, 2013

    Suzuki Akira, Uchizawa Kei, Zhou Xiao

    Multiple Authorship (Including Foreigners)

  • Hitori number, Fun with Algorithms. FUN 2012. Lecture Notes in Computer Science, 7288 334-345, 2012

    Akira Suzuki, Kei Uchizawa, Takeaki Uno

    Multiple Authorship (Only Japanese)

  • Lower bounds for linear decision trees via an energy complexity argument, Mathematical Foundations of Computer Science 2011. MFCS 2011. Lecture Notes in Computer Science, 6907 568-579, 2011.08

    Kei Uchizawa, Eiji Takimoto

    Multiple Authorship (Including Foreigners)

  • Size–energy tradeoffs for unate circuits computing symmetric Boolean functions, Theoretical Computer Science, 412(8-10) 773-782, 2011.03

    Kei Uchizawa, Eiji Takimoto, Takao Nishizeki

    Multiple Authorship (Including Foreigners)

  • Size-energy tradeoffs for unate circuits computing symmetric Boolean functions, THEORETICAL COMPUTER SCIENCE, 412(8-10) 773-782, 2011.03

    Uchizawa, K; Takimoto, E; Nishizeki, T

    Multiple Authorship (Only Japanese)

  • On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms, Computing and Combinatorics. COCOON 2011. Lecture Notes in Computer Science, 6842 86-97, 2011

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Multiple Authorship (Including Foreigners)

  • Energy and Fan-In of Threshold Circuits Computing Mod Functions, Theory and applications of models of computation, 6648 154-163, 2011

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Multiple Authorship (Including Foreigners)

  • Energy and depth of threshold circuits, Theoretical Computer Science, 411(44-46) 3938-3946, 2010

    Uchizawa, Kei and Nishizeki, Takao and Takimoto, Eiji

    Multiple Authorship (Including Foreigners)

  • Energy complexity and depth of threshold circuits, Fundamentals of Computation Theory. FCT 2009. Lecture Notes in Computer Science, 5699 335-345, 2009

    Kei Uchizawa, Takao Nishizeki, Eiji Takimoto

    Multiple Authorship (Including Foreigners)

  • Size and Energy of Threshold Circuits Computing Mod Functions, Mathematical Foundations of Computer Science 2009. MFCS 2009. Lecture Notes in Computer Science,, 5734 724-735, 2009

    Kei Uchizawa, Takao Nishizeki,Eiji Takimoto

    Multiple Authorship (Including Foreigners)

  • Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity, Theoretical Computer Science, 407(1-3) 474-487, 2008.11

    Kei Uchizawa, Eiji Takimoto

    Multiple Authorship (Including Foreigners)

  • On the Computational Power of Threshold Circuits with Sparse Activity, Neural Computation, 18(12) 2994-3008, 2006.12

    Kei Uchizawa, Rodney Douglas, Wolfgang Maass

    Multiple Authorship (Including Foreigners)

  • Energy complexity and entropy of threshold circuits, Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, 4051 631-642, 2006

    Kei Uchizawa, Rodney Douglas, Wolfgang Maass

    Multiple Authorship (Including Foreigners)

display all >>

Academic Awards Received

  • LA/EATCS Best Presentation Award, 2019.02, Japan

Grant-in-Aid for Scientific Research

  • Grant-in-Aid for Scientific Research(C)，2025.04 - 2028.03

  • Grant-in-Aid for Scientific Research(C)，2022.04 - 2025.03

  • Grant-in-Aid for Scientific Research(C)，2019.04 - 2022.03

  • Grant-in-Aid for Scientific Research(C)，2016.04 - 2019.03

  • Grant-in-Aid for Scientific Research(C)，2013.04 - 2016.03

  • Grant-in-Aid for Young Scientists(B)，2011 - 2012

display all >>

Other external funds procured

  • Foundation of algorithm designs for artificial neural networks，2019.04 - 2022.03，Foundation of algorithm designs for artificial neural networks

    We consider computational tasks of deciding if a given neural network possesses various predefined mathematical properties, and investigate how many computational resources are required to compute them. We then show that there exists a property for which it can be computationally very hard to check even if a given neural network is extremely simple (i.e., a neural network is of a single neuron). We also show that another property is computationally hard to check when a given neural network has two layers, while the property is easy to check (solvable in polynomial time) when a given neural network consists of a single neuron. Our results theoretically confirm that extracting information from multi-layer neural network can be computationally very hard.

    Japan Society for the Promotion of Science

  • Limitation of Threshold Circuits designed for Machine Learning，2016.04 - 2019.03，Limitation of Threshold Circuits designed for Machine Learning

    In this research, we theoretically investigate a question why neural networks of large depth obtained by a machine learning method show significant performance for various tasks. We consider a particular type of neural networks, called threshold circuits, and then provide mathematical proofs which suggest that large depth contributes to the performance of threshold circuits that carry out (somewhat artificial) information processing. As part of the proofs, we also show detailed constructions (that is, placement of neural computational elements and their connections) of threshold circuits that are guaranteed to be achieve good performance for the information processing.

    Japan Society for the Promotion of Science