DCASE 2020 Challenge Judges’ Award

Winners: Yuma Koizumi, NTT Media Intelligence Laboratories; Daiki Takeuchi, Yasunori Ohishi, Noboru Harada, Kunio Kashino, NTT Communication Science Laboratories

Date: November 1, 2020

Organization: DCASE (Detection and Classification of Acoustic Scenes and Events) Community

For “The NTT DCASE2020 Challenge Task 6 System: Automated Audio Captioning with Keywords and Sentence Length Estimation.”

Published as: Y. Koizumi, D. Takeuchi, Y. Ohishi, N. Harada, and K. Kashino, “The NTT DCASE2020 Challenge Task 6 System: Automated Audio Captioning with Keywords and Sentence Length Estimation,” DCASE2020 Challenge, Mar.–July 2020.

Certificate of Appreciation

Winner: Seishi Takamura, NTT Media Intelligence Laboratories

Date: December 31, 2020

Organization: The Institute of Electrical and Electronics Engineers (IEEE) Region 10

For his dedicated services and commitment as the 2019 & 2020 IEEE Region 10 Treasurer.

IEEE Fellow

Winner: Tomohiro Nakatani, NTT Communication Science Laboratories

Date: January 1, 2021

Organization: IEEE

For his contributions to far-field signal processing for speech enhancement and recognition.

Distributed Server Allocation Model with Preventive Start-time Optimization against Single Failure

S. Masuda, F. He, A. Kawabata, and E. Oki

Proc. of the IEEE 21st International Conference on High-Performance Switching and Routing (HPSR 2020), May 2020.

This paper proposes a distributed server allocation model with the preventive start-time optimization against a single server failure. The proposed model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming problem. We prove the NP (nondeterministic polynomial time)-completeness for the considered problem. The numerical results reveal that the proposed model reduces the largest maximum delay compared to one baseline; it avoids instability caused by the unnecessary disconnection, which frequently occurs in the other baseline.

Participating-domain Segmentation Based Server Selection Scheme for Real-time Interactive Communication

A. Kawabata, B. C. Chatterjee, and E. Oki

IEICE Transactions on Communications, Vol. E103-B, No. 7, pp. 736–747, July 2020.

This paper proposes an efficient server selection scheme in successive participation scenario with participating-domain segmentation. The scheme is utilized by distributed processing systems for real-time interactive communication to suppress the communication latency of a wide-area network. In the proposed scheme, users participate for server selection one after another. The proposed scheme determines a recommended server, and a new user selects the recommended server first. Before each user participates, the recommended servers are determined assuming that users exist in the considered regions. A recommended server is determined for each divided region to minimize the latency. The new user selects the recommended available server, where the user is located. We formulate an integer linear programming problem to determine the recommended servers. Numerical results indicate that, at the cost additional computation, the proposed scheme offers smaller latency than the conventional scheme. We investigate different policies to divide the users’ participation for the recommended server finding process in the proposed scheme.

Algorithms for Distributed Server Allocation Problem

T. Sawa, F. He, A. Kawabata, and E. Oki

IEICE Transactions on Communications, Vol. E103-B, No. 11, pp. 1341–1352, November 2020.

This paper proposes two algorithms, namely server-user matching (SUM) algorithm and extended server-user matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ESUM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.

Power of Uninitialized Qubits in Shallow Quantum Circuits

Y. Takahashi and S.Tani

Theoretical Computer Science, Vol. 851, pp. 129–153, January 2021.

We study uninitialized qubits, whose initial state is arbitrary and unknown, in relation to the computational power of shallow quantum circuits. To do this, we consider uniform families of shallow quantum circuits with n input qubits, O(logn) initialized ancillary qubits, and n^o(1) uninitialized ancillary qubits, where the input qubits only act as control qubits. We show that such a circuit with depth O((logn)²) can compute any symmetric Boolean function on n bits that is computable by a uniform family of polynomial-size classical circuits. Since it is unlikely that this can be done with only O(logn) initialized ancillary qubits, our result provides evidence that the presence of uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O(logn) initialized ancillary qubits. On the other hand, to understand the limitations of uninitialized qubits, we focus on sub-logarithmic-depth quantum circuits and show the impossibility of computing the parity function on n bits.

Graph-based Regional NMF for Distributed Computing

T. Koshizuka, K. Takeuchi, T. Matsubayashi, and H. Sawada

IPSJ Journal, Vol. 62, No. 1, pp. 387–396, January 2021.

Non-negative matrix factorization (NMF) is a popular unsupervised pattern recognition technique for the analysis of aggregated data. In particular, non-negative multiple matrix factorization (NMMF) treats common elements from multiple data as common factors, and execute simultaneous decomposition effectively. In this study, we propose a novel matrix factorization method called regional non-negative matrix factorization (rNMF), which factorises multiple matrics simultaneously, focusing on physical relation between aggregated data such as regional characteristics in addition to common factors. rNMF expresses data of physically close areas in a similar feature space, and extracts intuitively interpretable bases and coefficients from multiple matrics. The information of regional location is given by a graph. Furthermore, by solving the graph coloring problem heuristically, rNMF works at high speed on a distributed system even if the analyzed data are large matrices. In this paper, we formulate rNMF as an extended version of NMF and derive multiplicative update rules for parameter estimation. We performed experiment with real data, which were aggregated by region, in order to verify that rNMF can expresses adjacent regional data in a common feature, rNMF attained similar generalization performance as the original NMF, and rNMF works at high speed on a distributed system.

Optimal Server Selection Scheme with Optimistic Synchronization for Delay Sensitive Service

A. Kawabata, B. C. Chatterjee, and E. Oki

Proc. of the 18th IEEE Consumer Communications & Networking Conference (CCNC 2021), Virtual conference, January 2021.

In distributed processing for communication services, a proper server selection scheme is required to suppress delay by ensuring the event occurrence order. Although a conservative synchronization algorithm (CSA) has been used in this issue, an optimistic synchronization algorithm (OSA) can be a potential candidate for synchronizing distributed systems. In comparison with CSA, which reproduces events in occurrence order before processing application, OSA can be feasible to realize low delay communication as the processing events arrive sequentially. This paper proposes an optimal server selection scheme considering OSA for distributed processing systems to minimize end-to-end delay under the condition that the holding time for application status is limited. In other words, the endto-end delay is minimized based on the allowed rollback time for application design or quality-of-service. Numerical results indicate that the delay of the proposed scheme can be reduced by up to a quarter compared to that of the conventional scheme that is based on CSA.