Yaqiao Li 李雅樵 I am an Assistant Professor in SUAT深圳理工大学 in Shenzhen, China. NEWS! The following positions are available: Postdocs, PhD/Master, research visitors. Email: liyaqiao [at] suat-sz.edu.cn Education and Postdoc I was fortunately mentored by Jinpeng An, Hamed Hatami, Pierre McKenzie, Denis Pankratov and Lata Narayanan. Master in pure mathematics from Peking Univeristy, PhD in computer science from McGill university, Postdoc in University of Montreal and Concordia university. Research Below are illustration of some of my works.

Selected Publication (full list)

• Computational Complexity
• Yaqiao Li, Pierre McKenzie, Perspective on complexity measures targeting read-once branching programs, Information and Computation (2024). arXiv:2305.11276.
click for a Summary:

Branching program (aka, binary decision diagram) is a more flexible counterpart of decision tree that represents/computes Boolean functions. It is: (i) a basic model for studying computational space, (ii) closely related to pseudorandomness, (iii) a fundamental data structure, (iv) useful to synthesize circuits and in formal verification, etc.



This paper studied the minimum size of read-once branching programs from the perspective of proposing lower bound complexity measures, and demonstrated their strengths as well as limitations, such as on the Tseitin formula (which is applicable in proof complexity), and on the Tree Evaluation Problem (which is studied for understanding a fundamental open problem in complexity: Logspace vs Polytime), etc.





• Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li, Trading information complexity for error, CCC 2017, Theory of Computing Vol 14 (2018) Article 6 pp. 1-73. arXiv:1611.06650.
click for a Summary:

Information complexity, incorporating Shannon's information theory into communication models, is a continuous version of communication complexity. Initially, it was used to help study communication complexity, and later found many other applications such as in optimization and in circuit complexity, etc.



This paper, as the 1st part, initiated the basic theory of the dependency of information complexity on the error allowed in computation. This led to a more accurate formula of the randomized communication complexity of the important disjointness function, and a solution of an open problem of Braverman.







• Online Computation
• Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, Denis Pankratov, On the Online Weighted Non-Crossing Matching Problem, SWAT 2024.
click for a Summary:

Matching is a common task in nature, society, and mathematics. Avoiding crossing (of matching lines/curves) is a desired sometimes indispensable condition, such as for circuit design and understanding RNA structures, etc.



This paper introduced the online and weighted version of the non-crossing matching problem, and gave optimal or competitive online algorithms and lower bounds in various models. In particular, we found a beautiful 1/3-competitive randomized algorithm, which uses a binary tree to guide its matching decisions.





• Yaqiao Li, Denis Pankratov, Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections, LAGOS 2023, arXiv:2306.11241.
click for a Summary:

Bin packing is a classical NP-complete optimizaiton problem that is also of practical importance such as in loading cargo for shipping, creating file backups in media, etc.





This paper introduced the online incidence matrix associated with the online hypergraph, which naturally led to a simple reduction from online hypergraph coloring to online vector bin packing, thus simplified a previous breakthrough by Azar et. al.. This paper also showed a 'diverse' multi-family has an interesting intersecting property, thus resolved a conjecture on online hypergraph coloring by Nagy-György and Imreh.







• (pure) Mathematics
• Hamed Hatami, Pooya Hatami, Yaqiao Li, A characterization of functions with vanishing averages over products of disjoint sets, European J. Combin., vol 56 (2016) 81–93. arXiv:1411.2314.
click for a Summary:

Random graph is an important model in mathematics, physics, computer science, and in studying epidemics such as COVID-19. The Erdős–Rényi random graph has its edges generated independently with some probability p. A graph is quasi-random if it has similar statistics of subgraph-counts with the Erdős–Rényi random graph, e.g., the number of triangles should be close to n^3 p^3.



Although graphs seem combinatorial in nature, this paper used an analytic tool called Walsh expansion to understand the structure of functions satisfying certain integration property, the structure discovered led to resolving some of the conjectures on quasi-random graphs by Janson and Sós. Pierre Deligne (Fields Medalist) wrote a letter commenting our structure theorem.







• Social Science
• Yaqiao Li, Lata Narayanan, Jaroslav Opatrny, Yi Tian Xu, Diversity-seeking swap games in networks, submitted.
click for a Summary:

Diversity is observed to be beneficial in social and working environment, and UN calls biodiversity "our strongest natural defense against climate change". Darwin and Wallace already discovered that ecosystem diversity, via niche differentiation, supports higher productivity and better invasion resistance, than a monoculture. Schelling in his original study of segregation of residential neighborhoods (Dynamic models of segregation, 1971) has already, perhaps presciently, experimented diversity-seeking agents (of two types only), called "integrationist", and discovered "phenomena that are not present in the case of purely separatist demands", e.g., "integration requires more complex patterning than separation". Hayes (The Math of Segregation, 2013) observed that "the social fabric of segregation has begun to fray" and "the time has come for a model of racial reintegration".






This paper, parallel to the famous Schelling game, modelled diversity-seeking agents and studied their swap games, whose equilibria are measured by several diversity measures we proposed. The theory and simulation both showed that segregation would be effectively removed if agents become diversity-seeking, though strong diversity measures such as evenness is still hard to achieve.








• Dingyu Zhang, Yaqiao Li, Nadia Bhuiyan, A Tale of Two Organizational Structures, submitted.
click for a Summary:

An organization/team consists of diverse people often of distinct capabilities, this we call the team structure. A team makes its decision by aggregating individuals' decisions according to certain pre-speficied rules (e.g., polyarchy, hierarchy, committee, etc) , this we call the decision structure. If an organization has a fixed team, how should it chooses its decision structure? Similarly, if an organization has a fixed decision structure (e.g., cannot be easily changed), what types of people it should hire? More generally, if both sturctures are subject to design (e.g., for a new company), how does an organization systematically consider its various choices?






This paper, using university faculty hiring as a guiding example, modeled these two structures into one framework and studied carefully the interplay between the two, and how they together influence on an organization's performance. Some findings are surprising to the extent of counter-intuitive at the first sight.








• Intelligence
• Yi Tian Xu, Yaqiao Li, David Meger, Human motion prediction via pattern completion in latent representation space, CRV 2019. arXiv:1904.09039.
click for a Summary:

Knowledge of how humans move can help intelligent robots in tasks involving an interactive human environment, such as navigating through a crowded street, or playing sports or tabletop games with humans.



This paper, inspired by ideas in cognitive science, proposed a new and general approach to solve human motion understanding via pattern completion on a learned latent representation space. Our model outperforms current state-of-the-art in human motion prediction across a number of tasks, with no customization. The architecture uses a new and generic autoencoder based on sequence-to-sequence learning. See here for more introduction of this work by the first author Yi Tian Xu.

Teaching

• COMP 6651: Algorithm Design Techniques, Concordia, 2023/01 to 2023/04.


• Discrete Mathematics, SMBU, 2022/03 to 2022/06.


• COMP/MATH 552 Combinatorial Optimization, McGill, 2018/01 to 2018/04.