The talk is going to be given in Japanese.
Time: Friday, April 18, 2025 at 16:45-18:15
Method: Zoom and PandA
– The URL of Zoom will be announced via faculty’s mailing list 3 days
before the colloquium.
– The lecture material will be available in PandA at 16:15 on the day
of the colloquium.
– Note that there will be no recording and streaming of any lectures at this year’s colloquium.
Speaker: Prof. Yutaka MASUDA
(Graduate School of Informatics, Nagoya University ・ Associate Professor)
Title:
Design and Verification of Approximate Computing Circuit
Abstract:
Approximate computing is gaining attention as a promising approach to
enhancing the energy efficiency of digital systems across a wide range
of application domains, including digital signal processing, image,
audio, and video processing, graphics, wireless communications, and
machine learning. While conventional design paradigms assume that all
computations must be performed with complete accuracy, approximate
computing allows for a controlled degree of computational error. This
relaxation enables the omission or simplification of certain operations,
reducing software processing time and improving hardware efficiency in
area and power consumption. In this talk, I will present recent research
trends in the design and verification of approximate computing circuits.
今回の講演は日本語で行われます．
日時: 2025年 4月 18日(金) 16:45-18:15
手段: ZoomおよびPandA
ZoomのURLは開催3日前に研究科メーリングリストでお知らせします．
講演資料は開催当日の16時15分にPandAに掲載します．
今年度の談話会では，講演の録画・ストリーミング配信は一切行いません．
講演者: 増田 豊 先生
(名古屋大学 大学院情報学研究科・准教授)
講演タイトル:
近似コンピューティング回路の設計検証
概要:
近似コンピューティングは、デジタル信号処理、画像・音声・映像処理、グラフィックス、無線通信、機械学習などの幅広い応用分野において、集積システムのエネルギー効率を高める有望なアプローチとして注目を集めている。従来の設計パラダイムは全ての計算を正確に実行することを前提とする一方、近似コンピューティングでは一定の演算誤差を許容する。これにより、計算処理の省略や簡略化が可能となり、ソフトウェアの処理時間削減、および、ハードウェアの省面積化や低消費電力化を推進できる。本講演では、近似コンピューティング回路の設計と検証における最近の研究動向について紹介する。
The talk is going to be given in English.
Time: Friday, May 23, 2025 at 16:45–18:15
Method: Zoom and PandA
– The URL of Zoom will be announced via faculty’s mailing list 3 days before the colloquium.
– The lecture material will be available in PandA at 16:15 on the day of the colloquium.
– Note that there will be no recording and streaming of any lectures at this year’s colloquium.
Speaker: Dr. Shashanka Kulamarva
(Program-Specific Researcher, Minato Lab, Kyoto University)
Title: Acyclic Edge Coloring and Burning Number of a Graph
Abstract:
An acyclic edge coloring of a graph is a proper edge coloring with no bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum integer k such that G has an acyclic edge coloring with k colors. It was conjectured by Fiamˇc´ık that a′(G) ≤ Δ+2 for any graph G with maximum degree Δ. A graph is said to be chordless if no cycle in the graph contains a chord. Machado et al. proved that the chromatic index of a chordless graph is Δ when Δ ≥ 3. We prove that for any chordless graph G, a′(G) = Δ, when Δ ≥ 3. To obtain the result on acyclic chromatic index, we prove a structural result on chordless graphs which is a refinement of the structure given by Machado et al. in case of chromatic index.
For an undirected graph G, graph burning is defined as follows: at step t = 0 all vertices in G are unburned. At each step t ≥ 1, one new unburned vertex is selected to burn until we exhaust all the vertices. If a vertex is burned at step t, then all its unburned neighbors are burned in step t+1, and the process continues until there are no unburned vertices in G. The burning number of a graph G, denoted by b(G), is the minimum number of steps required to burn all the vertices of G. The Burning Number problem (BNP) asks whether the burning number of an input graph G is at most k or not. We study the BNP both from an algorithmic and a structural point of view. The BNP is known to be NP-complete for trees with maximum degree at most three and interval graphs. We prove that this problem is NP-complete even when restricted to connected cubic graphs and connected proper interval graphs. The well-known burning number conjecture asserts that all the vertices of a graph of order n can be burned in ⌈√n ⌉ steps. We also study two variants of the problem, namely edge burning (only edges are burned) and total burning (both vertices and edges are burned). In particular, we establish their relationship with the burning number problem and evaluate the algorithmic complexity of these variants. A bipartite graph G = (A, B, E) is said to be a biconvex bipartite graph if there exist orderings
今回の講演は英語で行われます．
日時: 2025年5月23日(金) 16:45-18:15
手段: ZoomおよびPandA
ZoomのURLは開催3日前に研究科メーリングリストでお知らせします．
講演資料は開催当日の16時15分にPandAに掲載します．
今年度の談話会では，講演の録画・ストリーミング配信は一切行いません．
講演者: Shashanka Kulamarva 様
(湊研究室研究員)
講演タイトル:
Acyclic Edge Coloring and Burning Number of a Graph
概要:
An acyclic edge coloring of a graph is a proper edge coloring with no bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum integer k such that G has an acyclic edge coloring with k colors. It was conjectured by Fiamˇc´ık that a′(G) ≤ Δ+2 for any graph G with maximum degree Δ. A graph is said to be chordless if no cycle in the graph contains a chord. Machado et al. proved that the chromatic index of a chordless graph is Δ when Δ ≥ 3. We prove that for any chordless graph G, a′(G) = Δ, when Δ ≥ 3. To obtain the result on acyclic chromatic index, we prove a structural result on chordless graphs which is a refinement of the structure given by Machado et al. in case of chromatic index.
For an undirected graph G, graph burning is defined as follows: at step t = 0 all vertices in G are unburned. At each step t ≥ 1, one new unburned vertex is selected to burn until we exhaust all the vertices. If a vertex is burned at step t, then all its unburned neighbors are burned in step t+1, and the process continues until there are no unburned vertices in G. The burning number of a graph G, denoted by b(G), is the minimum number of steps required to burn all the vertices of G. The Burning Number problem (BNP) asks whether the burning number of an input graph G is at most k or not. We study the BNP both from an algorithmic and a structural point of view. The BNP is known to be NP-complete for trees with maximum degree at most three and interval graphs. We prove that this problem is NP-complete even when restricted to connected cubic graphs and connected proper interval graphs. The well-known burning number conjecture asserts that all the vertices of a graph of order n can be burned in ⌈√n ⌉ steps. We also study two variants of the problem, namely edge burning (only edges are burned) and total burning (both vertices and edges are burned). In particular, we establish their relationship with the burning number problem and evaluate the algorithmic complexity of these variants. A bipartite graph G = (A, B, E) is said to be a biconvex bipartite graph if there exist orderings