IQC Math and CS seminar featuring Daiki Suruga

Thursday, October 2, 2025 3:00 pm - 4:00 pm EDT (GMT -04:00)
Export this event to calendar
iCal

Random Unitaries in Constant (Quantum) Time

Daiki Suruga | Nagoya University

In this talk, I will investigate some of my works related to communication and query complexity. The contents of the talk may be divided into the following three parts:

  1. Tight bounds on symmetric predicates in quantum communication complexity.

    In (two-party) quantum communication complexity, Set-disjointness function is the most well-studied function, and is an example of an important family of problems, namely symmetric AND functions. In this talk, we firstly give tight bounds for any of symmetric AND functions. Based on: Matching upper bounds on symmetric predicates in quantum communication complexity

  2. On multiparty quantum communication complexity.

    We can naturally generalize two-party communication complexity to a multiparty scenario. However, the existing proof techniques for the two-party setting does not naturally fit into the multiparty setting; a new technique must be necessary. In this work, we impose a mild condition on the multiparty communication model, and under the condition, we prove tight bounds for several important functions such as multiparty set-disjointness function. Based on: Bounds on oblivious multiparty quantum communication complexity

  3. Direct sum theorem beyond query complexity.

    A fundamental question in computer science is: Is it harder to solve n instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has received much attention in several research fields including query complexity, communication complexity and information theory. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: establishing a complete characterization of the amortized query/oracle complexities. Based on: Direct sum theorems beyond query complexity

Location