Updated on 2026/06/26

写真a

 
UCHIZAWA Kei
 
Title
Associate Professor

Research Areas

  • Informatics / Theory of informatics

 

Papers

  • Upper bound for output patterns of energy-bounded boolean circuits, and its applications, Acta Informatica, 63 21, 2026.06

    J. Sarma, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • On saving energy in boolean circuits via negations, Proc. 25th International Symposium Fundamentals of Computation Theory, 391-405, 2025.09

    J. Sarma, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Trade-offs between energy and depth of neural networks, Neural Computation, 36(8) 1541-1567, 2024.07

    K. Uchizawa, H. Abe

    Multiple Authorship (Only Japanese)

  • Energy and output patterns in Boolean circuits, Proc. 18th Annual Conference on Theory and Applications of Models of Computation, 14637 185-196, 2024.05

    J. Sarma, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Exponential lower bounds for threshold circuits of sub-linear depth and energy, Proc. 48th International Symposium on Mathematical Foundations of Computer Science, 85, 2023.08

    K. Uchizawa

    Single Author

  • Synchronous Boolean finite dynamical systems on directed graphs over XOR functions, Theory of Computing Systems, 67(3) 569-591, 2023.06

    M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • An O(n^2)-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

    Y. Kobayashi, S. Nakano, K. Uchizawa, T. Uno, Y. Yamaguchi, K. Yamanaka

    Multiple Authorship (Only Japanese)

  • A generalization of spatial Monte Carlo integration, Neural Computation, 33(4) 1-26, 2021.01

    M. Yasuda, K. Uchizawa

    Multiple Authorship (Only Japanese)

  • Size, depth and energy of threshold circuits computing parity function, Proc. 31st International Symposium on Algorithms and Computation, 54-(13pp.), 2020.12

    K. Uchizawa

    Single Author

  • Synchronous boolean finite dynamical systems on directed graphs over XOR functions, Proc. 45th International Symposium on Mathematical Foundations of Computer Science, 76-(13pp.), 2020.08

    M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Mind the mind with synchronous clocks, Proc. 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 71-72, 2019.09

    T. Horiyama, K. Kurita, Y. Okamoto, K. Uchizawa and R. Uehara

    Multiple Authorship (Only Japanese)

  • Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs, Theoretical Computer Science, 762 25-40, 2019.03

    A. Kawachi, M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Computational power of threshold circuits of energy at most two, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Discrete Mathematics and Its Applications, 101-A(9) 1431-1439, 2018.09

    H. Maniwa, T. Oki, A. Suzuki, K. Uchizawa, X. Zhou

    Multiple Authorship (Only Japanese)

  • Generalized predecessor existence problems for boolean finite dynamical systems, Proc. 42nd International Symposium on Mathematical Foundations of Computer Science, 83 8-(13pp.), 2017.12

    A. Kawachi, M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, Information and Computation, 256 226-236, 2017.10

    M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Hitori numbers, Journal of Information Processing, 25 695-707, 2017.01

    A. Suzuki, M. Kiyomi, Y. Otachi, K. Uchizawa, T. Uno

    Multiple Authorship (Only Japanese)

  • Threshold circuits detecting global patterns in two-dimensional maps, Journal of Graph Algorithms and Applications, 20(1) 115-131, 2016.02

    K. Uchizawa, D. Yashima, X. Zhou

    Multiple Authorship (Only Japanese)

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

    K. Yamanaka, E. D Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, T. Uno

    Multiple Authorship (Only Japanese)

  • Threshold circuits for global patterns in 2-dimensional maps, Proc. 9th International Workshop on Algorithms and Computation, 8973 306-316, 2015.02

    K. Uchizawa, D. Yashima, X. Zhou

    Multiple Authorship (Only Japanese)

  • Lower bounds for linear decision trees with bounded weights, Proc. 41st International Conference on Current Trends in Theory and Practice of Computer Science, 8939 412-422, 2015.01

    K. Uchizawa, E. Takimoto

    Multiple Authorship (Only Japanese)

  • Competitive diffusion on weighted graphs, Proc. 14th International Symposium on Algorithms and Data Structures, 422-433, 2015.01

    T. Ito, Y. Otachi, T. Saitoh, H. Satoh, A. Suzuki, K. Uchizawa, R. Uehara, K. Yamanaka, X. Zhou

    Multiple Authorship (Only Japanese)

  • Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems, Proc. 12th Annual Conference on Theory and Applications of Models of Computation, 9076 87-98, 2015.01

    M. Ogihara, K. Uchizawa

    Multiple Authorship (Including Foreigners)

  • Generalized rainbow connectivity of graphs, Theoretical Computer Science, 555 35-42, 2014.10

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

    Multiple Authorship (Only Japanese)

  • Swapping labeled tokens on graphs, Proc. 7th International Conference on Fun with Algorithms, 364-375, 2014.07

    K. Yamanaka, E. D Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, T. Uno

    Multiple Authorship (Including Foreigners)

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

    K. Uchizawa

    Single Author

  • On the rainbow connectivity of graphs: Complexity and FPT algorithms, Algorithmica, 67(2) 161-179, 2013.09

    K. Uchizawa, T. Aoki, T. Ito, A. Suzuki

    Multiple Authorship (Including Foreigners)

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

    A. Suzuki , K. Uchizawa, X. Zhou

    Multiple Authorship (Only Japanese)

  • Energy-efficient threshold circuits detecting global pattern in 1-dimentional arrays, Proc. 10th Annual Conference on Theory and Applications of Models of Computation, 7876 248-259, 2013.05

    A. Suzuki, K. Uchizawa, X. Zhou

    Multiple Authorship (Only Japanese)

  • Generalized rainbow connectivity of graphs, Proc. 7th International Workshops on Algorithms and Computation, 233-244, 2013.02

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

    Multiple Authorship (Only Japanese)

  • Complexity of counting output patterns of logic circuits, Proc. 19th Computing: The Australasian Theory Symposium, 37-41, 2013.01

    K. Uchizawa, Z. Wang, H. Morizumi, X. Zhou

    Multiple Authorship (Only Japanese)

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

    A. Suzuki, K. Uchizawa, X. Zhou

    Multiple Authorship (Including Foreigners)

  • Energy-efficient threshold circuits for comparison functions , Interdisciplinary Information Sciences, 18(2) 161-166, 2012.12

    K. Uchizawa, X. Zhou

    Multiple Authorship (Only Japanese)

  • Hitori number, Proc. 6h International Conference on Fun with Algorithms, 334-345, 2012.06

    A. Suzuki, K. Uchizawa, T. Uno

    Multiple Authorship (Only Japanese)

  • Lower bounds for linear decision trees via an energy complexity argument, Proc. 36th International Conference on Mathematical Foundations of Computer Science, 568-579, 2011.08

    K. Uchizawa, E. Takimoto

    Multiple Authorship (Including Foreigners)

  • On the rainbow connectivity of graphs: complexity and FPT algorithms, Proc. 7th International Computing and Combinatorics Conference, 86-97, 2011.08

    K. Uchizawa, T. Aoki, T. Ito, A. Suzuki, X. Zhou

    Multiple Authorship (Only Japanese)

  • Energy-efficient threshold circuits computing MOD functions, Proc. 17th Computing: the Australasian Theory Symposium, 105-110, 2011.08

    A. Suzuki, K. Uchizawa, X. Zhou

    Multiple Authorship (Including Foreigners)

  • Energy and fan-in of threshold circuits computing mod functions, Proc. 8th Annual Conference on Theory and Applications of Models of Computation, 154-163, 2011.05

    A. Suzuki, K. Uchizawa, X. Zhou

    Multiple Authorship (Including Foreigners)

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

    K. Uchizawa, E. Takimoto, T. Nishizeki

    Multiple Authorship (Including Foreigners)

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

    K. Uchizawa, T. Nishizeki, E. Takimoto

    Multiple Authorship (Including Foreigners)

  • Energy complexity and depth of threshold circuits, Proc. 17th International Symposium on Fundamentals of Computation Theory, 335-345, 2009.09

    K. Uchizawa, T. Nishizeki, E. Takimoto

    Multiple Authorship (Including Foreigners)

  • Size and energy of threshold circuits computing mod functions, Proc. 34th International Symposium Mathematical Foundations of Computer Science, 724-735, 2009.08

    K. Uchizawa, T. Nishizeki, E. 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

    K. Uchizawa, E. Takimoto

    Multiple Authorship (Including Foreigners)

  • An exponential lower bound on the size of constant-depth threshold circuits with small energy complexity, Proc. 22nd Annual IEEE Conference on Computational Complexity, 169-178, 2007.06

    K. Uchizawa, E. Takimoto

    Single Author

  • On the computational power of threshold circuits with sparse activity, Neural Computation, 18(12) 2994-3008, 2006.12

    K. Uchizawa, R. Douglas, W. Maass

    Multiple Authorship (Including Foreigners)

  • Energy complexity and entropy of threshold circuits, Proc. 33rd International Colloquium on Automata, Languages and Programming, 4051 631-642, 2006.07

    K. Uchizawa, R. Douglas, W. Maass

    Multiple Authorship (Only Japanese)

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