LAB LOGA page on LabLog, a review site (not the lab's official page)
Applied Mathematics Lab (Kazuhisa Makino)
Machine-translated · View original
A lab on optimization and algorithms that exploits discrete structures such as graphs and combinatorial objects.
AboutAbout the lab
From discrete structures to optimization and algorithms.
The Makino Lab analyzes discrete structures such as those in graph theory and combinatorics, and studies optimization and algorithms that exploit those structures.
Its representative research is on the dualization problem for monotone Boolean functions.
This problem is known to be equivalent, in the sense of polynomial-time reductions, to many problems arising in diverse fields such as mathematical programming, artificial intelligence, databases, distributed systems, and learning theory.
The lab also studies systems of integer linear inequalities, complementarity problems, online optimization problems, robust optimization, and equilibria in game theory.
Key terms
- Monotone Boolean function
- A Boolean function whose output never changes from 1 to 0 when any of its inputs is changed from 0 to 1.
- Algorithm
- A procedure or set of rules of computation by which a computer is made to carry out processing.
- Polynomial time
- Computation time bounded by a polynomial in the size of the input. It is a rough measure of whether a problem can be solved efficiently.
NewsLab news
Prof. Makino was elected a Fellow of the Information Processing Society of Japan
Prof. Makino received the FIT Funai Best Paper Award
ResearchResearch themes
The lab studies the analysis of discrete structures such as those in graph theory and combinatorics, as well as optimization and algorithms that exploit those structures. It works on the dualization problem for monotone Boolean functions and the problem of completing logical hypotheses in inference.
*Illustrative imageDualization of monotone Boolean functions
Given a conjunctive normal form, the problem is to find an equivalent monotone disjunctive normal form. Fredman and Khachiyan showed that it can be solved in quasi-polynomial time, but whether it can be solved in polynomial time is still unknown.
*Illustrative imageCompleting logical hypotheses in Horn inference
In joint research on the problem of completing logical hypotheses in inference, the lab overturned a widely believed conjecture and showed that it can be done in incremental polynomial time for Horn inference, the most important class.
MembersFaculty
- ProfessorKazuhisa Makino
VoicesStudent voices
Ratings and reviews reflect the experiences of individual current or former students, not the lab's official views. Whether a lab has reviews, or how many, says nothing about the lab itself.
Students who take part in an interview may receive a thank-you gift worth ¥1,000, regardless of what they say.
Student ratings (0 students)
--
--
--
--
--
--
Student voices answer questions like these
- What's great about this lab?
- What did you learn after joining?
- What's the vibe, and what is the professor like?
- Who is this lab for?
- Where do graduates go?
Your experience can help younger students choose their lab. Your name won't be shown.
Write a lab reviewAnonymous · Your draft is saved if you stopRelatedLabs similar to Applied Mathematics Lab (Kazuhisa Makino)
Applied Mathematics Division (Kobayashi) LabResearch Institute for Mathematical Sciences, Division of Applied Mathematical SciencesApplied mathematics and computational science / discrete mat…
Applied Mathematics Division (Kawamura) LabResearch Institute for Mathematical Sciences, Division of Applied Mathematical SciencesComputer science / theory of computation (computability and …
Applied Mathematics Lab (Masahito Hasegawa)Research Institute for Mathematical Sciences, Division of Applied Mathematical SciencesComputer science / theoretical computer science, software sc…
Isono LabResearch Institute for Mathematical Sciences, Division of Applied Mathematical SciencesAnalysis / operator algebras and ergodic theory (von Neumann…The information on this page is compiled by the LabLog team from the lab's public information and interviews. For corrections or removal requests, please contact LabLog, not the lab.
Report an errorAbout the images
The top and research theme images are illustrative and were not taken at the lab. They are cropped from Wikimedia Commons images. Cropped CC BY-SA images are provided under the same CC BY-SA license as the original (version shown on each line).
- Top image: “B functies 2var versie02” Bob.v.R / CC BY-SA 4.0 (cropped)
- Dualization of monotone Boolean functions: “Simple adder on logic gates” LISnapyc / CC BY-SA 4.0 (cropped)
- Completing logical hypotheses in Horn inference: “In Quest of Univeral Logic HypoSyll” Arman Kashef / CC BY-SA 4.0 (cropped)
- Related lab (応用数理研究部門
（小林 佑輔） ): “Graph-matroid” Didia / CC BY-SA 4.0 (cropped) - Related lab (応用数理研究部門
（河村 彰星） ): “Turing Machine” Porao / Public domain (cropped) - Related lab (応用数理研究部門
（長谷川 真人） ): “Kleisli Category - morphism composition” AugPi / CC BY-SA 4.0 (cropped) - Related lab (応用数理研究部門
（磯野 優介） ): “Bernoullishift” Andreas Mandl / CC BY-SA 3.0 (cropped)
About LabLog
LabLog is a lab review app for students only. Student members at each university interview students in labs and publish what they say. Student voices can only be read by students who sign up with a university email address. Operated by bestiee Inc.
Learn more about LabLog ↗Search engines and AI may reference the basic lab info and rating summaries on this page and the description of LabLog. Student voices are for student members only. Automated collection by programs (scraping, or input to or training of AI) is prohibited under Article 8 of the Terms of Service. If you need data for research or analysis, please contact us.