Author name cluster

Yuyi Wang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

1 author row

AAMAS Conference 2026 Conference Paper

First-Order and Second-Order Model Counting Meet Stable Marriages, Stable Roommates, and Stable Diners

Václav Kula
Jan Tóth
Yuanhong Wang
Yuyi Wang
Ondrej Kuželka

We study the computational complexity of counting and sampling variants of classical stable matching problems, including the stable marriage, stable roommates, and stable seating arrangement problems. While these problems are generally intractable, we show that many become tractable when the agents’ preferences are drawn from only 𝑘 distinct classes. Our positive results build on recent advances in first-order and second-order model counting from the finite model theory literature. In particular, we demonstrate how these tools both extend recent positive results and resolve an open question about stable seating arrangements posed by Berriaud, Constantinescu, and Wattenhofer (Stable Dinner Party Seating Arrangements, WINE 2023).

PDF

AAAI Conference 2026 Conference Paper

Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence

Václav Kůla
Qipeng Kuang
Yuyi Wang
Yuanhong Wang
Ondřej Kuželka

The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on evidence—fixing the truth values of a set of ground literals—has been shown impossible in time polynomial in the domain size (unless ♯P ⊆ FP) even for fragments of logic that are otherwise tractable for WFOMC without evidence. In this work, we address the barrier by restricting the binary evidence to the case where the underlying Gaifman graph has bounded treewidth. We present a polynomial-time algorithm in the domain size for computing WFOMC for the two-variable fragments??² and?² conditioned on such binary evidence. Furthermore, we show the applicability of our algorithm in combinatorial problems by solving the stable seating arrangement problem on bounded-treewidth graphs of bounded degree, which was an open problem. We also conducted experiments to show the scalability of our algorithm compared to the existing model counting solvers.

PDF Details DOI

I&C Journal 2026 Journal Article

Variable version Lovász local lemma: A tale of two boundaries

Kun He
Liang Li
Xingwu Liu
Yuyi Wang
Mingji Xia

Shearer gave a tight criterion for the abstract version of the Lovász Local Lemma (abstract-LLL), but the corresponding picture for the variable version (variable-LLL), where events are generated from independent random variables, has remained largely open. We establish a necessary and sufficient criterion for variable-LLL expressed purely in terms of the event probabilities and the event-variable bigraph. This allows us to determine exactly the probability boundary for two fundamental families of event-variable graphs: cyclic and treelike bigraphs, giving the first nontrivial cases where the variable-LLL boundary is fully characterized. As a byproduct, we obtain a general constructive procedure that, for any given probability vector and event-variable graph, produces a set of events whose union has maximum possible probability; the method also applies when any two events are either independent or disjoint. We further show that computing the variable-LLL boundary is #P-hard in general, and focus on deciding whether there is a gap between the variable-LLL boundary and the corresponding abstract-LLL (Shearer) boundary. We prove that gap existence can be decided without evaluating Shearer's condition or our criterion. Using this theorem, we show that there is no gap when the base graph of the event-variable graph is a tree, whereas any induced cycle of length at least four forces a gap. Finally, we develop reduction rules that propagate gapful/gapless property and apply them to several combinatorial event-variable graphs.

Details DOI

NeurIPS Conference 2025 Conference Paper

AngleRoCL: Angle-Robust Concept Learning for Physically View-Invariant Adversarial Patches

Wenjun Ji
Yuxiang Fu
Luyang Ying
Deng-Ping Fan
Yuyi Wang
Ming-Ming Cheng
Ivor Tsang
Qing Guo

Cutting-edge works have demonstrated that text-to-image (T2I) diffusion models can generate adversarial patches that mislead state-of-the-art object detectors in the physical world, revealing detectors' vulnerabilities and risks. However, these methods neglect the T2I patches' attack effectiveness when observed from different views in the physical world (i. e. , angle robustness of the T2I adversarial patches). In this paper, we study the angle robustness of T2I adversarial patches comprehensively, revealing their angle-robust issues, demonstrating that texts affect the angle robustness of generated patches significantly, and task-specific linguistic instructions fail to enhance the angle robustness. Motivated by the studies, we introduce Angle-Robust Concept Learning (AngleRoCL), a simple and flexible approach that learns a generalizable concept (i. e. , text embeddings in implementation) representing the capability of generating angle-robust patches. The learned concept can be incorporated into textual prompts and guides T2I models to generate patches with their attack effectiveness inherently resistant to viewpoint variations. Through extensive simulation and physical-world experiments on five SOTA detectors across multiple views, we demonstrate that AngleRoCL significantly enhances the angle robustness of T2I adversarial patches compared to baseline methods. Our patches maintain high attack success rates even under challenging viewing conditions, with over 50% average relative improvement in attack effectiveness across multiple angles. This research advances the understanding of physically angle-robust patches and provides insights into the relationship between textual concepts and physical properties in T2I-generated contents. We released our code at https: //github. com/tsingqguo/anglerocl.

PDF Details

NeurIPS Conference 2025 Conference Paper

Constant Bit-size Transformers Are Turing Complete

Qian Li
Yuyi Wang

We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This improves previous works, which require scaling up either the model's precision or the number of parameters on longer inputs. Furthermore, we prove that the complexity class SPACE$[s(n)]$ exactly characterizes the expressive power of a constant bit-size transformer with a context window of length $s(n)$. Our approach relies on simulating Post machines, a Turing-complete computational model. Post machines can be modeled as automata equipped with a queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.

PDF Details

AIJ Journal 2024 Journal Article

Lifted algorithms for symmetric weighted first-order model sampling

Yuanhong Wang
Juhua Pu
Yuyi Wang
Ondřej Kuželka

Weighted model counting (WMC) is the task of computing the weighted sum of all satisfying assignments (i. e. , models) of a propositional formula. Similarly, weighted model sampling (WMS) aims to randomly generate models with probability proportional to their respective weights. Both WMC and WMS are hard to solve exactly, falling under the #P-hard complexity class. However, it is known that the counting problem may sometimes be tractable, if the propositional formula can be compactly represented and expressed in first-order logic. In such cases, model counting problems can be solved in time polynomial in the domain size, and are known as domain-liftable. The following question then arises: Is it also the case for WMS? This paper addresses this question and answers it affirmatively. Specifically, we prove the domain-liftability under sampling for the two-variables fragment of first-order logic with counting quantifiers in this paper, by devising an efficient sampling algorithm for this fragment that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of cardinality constraints. To empirically validate our approach, we conduct experiments over various first-order formulas designed for the uniform generation of combinatorial structures and sampling in statistical-relational models. The results demonstrate that our algorithm outperforms a state-of-the-art WMS sampler by a substantial margin, confirming the theoretical results.

Details DOI

IJCAI Conference 2023 Conference Paper

On Discovering Interesting Combinatorial Integer Sequences

Martin Svatoš
Peter Jung
Jan Tóth
Yuyi Wang
Ondřej Kuželka

We study the problem of generating interesting integer sequences with a combinatorial interpretation. For this we introduce a two-step approach. In the first step, we generate first-order logic sentences which define some combinatorial objects, e. g. , undirected graphs, permutations, matchings etc. In the second step, we use algorithms for lifted first-order model counting to generate integer sequences that count the objects encoded by the first-order logic formulas generated in the first step. For instance, if the first-order sentence defines permutations then the generated integer sequence is the sequence of factorial numbers n! . We demonstrate that our approach is able to generate interesting new sequences by showing that a non-negligible fraction of the automatically generated sequences can actually be found in the Online Encyclopaedia of Integer Sequences (OEIS) while generating many other similar sequences which are not present in OEIS and which are potentially interesting. A key technical contribution of our work is the method for generation of first-order logic sentences which is able to drastically prune the space of sentences by discarding large fraction of sentences which would lead to redundant integer sequences.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Domain-Lifted Sampling for Universal Two-Variable Logic and Extensions

Yuanhong Wang
Timothy van Bremen
Yuyi Wang
Ondřej Kuželka

Given a first-order sentence Γ and a domain size n, how can one sample a model of Γ on the domain t1, .. ., nu efficiently as n scales? We consider two variants of this problem: the uniform sampling regime, in which the goal is to sample a model uniformly at random, and the symmetric weighted sampling regime, in which models are weighted according to the number of groundings of each predicate appearing in them. Solutions to this problem have applications to the scalable generation of combinatorial structures, as well as sampling in several statistical-relational models such as Markov logic networks and probabilistic logic programs. In this paper, we identify certain classes of sentences that are domainliftable under sampling, in the sense that they admit a sampling algorithm that runs in time polynomial in n. In particular, we prove that every sentence of the form @x@y: ψpx, yq for some quantifier-free formula ψpx, yq is domain-liftable under sampling. We then further show that this result continues to hold in the presence of one or more cardinality constraints as well as a single tree axiom constraint.

PDF Details

NeurIPS Conference 2022 Conference Paper

Efficient Submodular Optimization under Noise: Local Search is Robust

Lingxiao Huang
Yuyi Wang
Chunxue Yang
Huanjian Zhou

The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by Hassidim and Singer (2017). For a cardinality constraint, we propose an algorithm achieving a near-optimal (1-1/e-O(epsilon))-approximation guarantee (for arbitrary epsilon > 0) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of Singer and Hassidim (2018). For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.

PDF Details

IJCAI Conference 2021 Conference Paper

Fast Algorithms for Relational Marginal Polytopes

Yuanhong Wang
Timothy van Bremen
Juhua Pu
Yuyi Wang
Ondrej Kuzelka

We study the problem of constructing the relational marginal polytope (RMP) of a given set of first-order formulas. Past work has shown that the RMP construction problem can be reduced to weighted first-order model counting (WFOMC). However, existing reductions in the literature are intractable in practice, since they typically require an infeasibly large number of calls to a WFOMC oracle. In this paper, we propose an algorithm to construct RMPs using fewer oracle calls. As an application, we also show how to apply this new algorithm to improve an existing approximation scheme for WFOMC. We demonstrate the efficiency of the proposed approaches experimentally, and find that our method provides speed-ups over the baseline for RMP construction of a full order of magnitude.

PDF Details DOI

I&C Journal 2021 Journal Article

Query complexity of generalized Simon's problem

Zekun Ye
Yunqi Huang
Lvzhou Li
Yuyi Wang

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP ( p, n, k ), is a natural extension of Simon's problem: Given a function f: Z p n → X where X is a finite set and the promise that for any x, y ∈ Z p n, f ( x ) = f ( y ) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k < n, the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O ( n − k ). However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP ( p, n, k ) has to query at least Ω ( max ⁡ { k, p n − k } ) values and any classical nonadaptive deterministic algorithm for GSP ( p, n, k ) has to query at least Ω ( max ⁡ { k, k ⋅ p n − k } ) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O ( max ⁡ { k, k ⋅ p n − k } ) on the classical deterministic query complexity of GSP ( p, n, k ), by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem.

Details DOI

AAAI Conference 2020 Conference Paper

Improving Neural Relation Extraction with Positive and Unlabeled Learning

Zhengqiu He
Wenliang Chen
Yuyi Wang
Wei Zhang
Guanchun Wang
Min Zhang

We present a novel approach to improve the performance of distant supervision relation extraction with Positive and Unlabeled (PU) Learning. This approach ﬁrst applies reinforcement learning to decide whether a sentence is positive to a given relation, and then positive and unlabeled bags are constructed. In contrast to most previous studies, which mainly use selected positive instances only, we make full use of unlabeled instances and propose two new representations for positive and unlabeled bags. These two representations are then combined in an appropriate way to make bag-level prediction. Experimental results on a widely used real-world dataset demonstrate that this new approach indeed achieves significant and consistent improvements as compared to several competitive baselines.

PDF Details

AAAI Conference 2019 Conference Paper

High Dimensional Clustering with r-nets

Georgia Avarikioti
Alain Ryser
Yuyi Wang
Roger Wattenhofer

Clustering, a fundamental task in data science and machine learning, groups a set of objects in such a way that objects in the same cluster are closer to each other than to those in other clusters. In this paper, we consider a well-known structure, so-called r-nets, which rigorously captures the properties of clustering. We devise algorithms that improve the runtime of approximating r-nets in high-dimensional spaces with `1 and `2 metrics from Õ(dn2−Θ( √ ) ) to Õ(dn + n2−α ), where α = Ω( 1/3 /log(1/ )). These algorithms are also used to improve a framework that provides approximate solutions to other high dimensional distance problems. Using this framework, several important related problems can also be solved efficiently, e. g. , (1 + )-approximate kth-nearest neighbor distance, (4 + )-approximate Min-Max clustering, (4+ )-approximate k-center clustering. In addition, we build an algorithm that (1 + )-approximates greedy permutations in time Õ((dn + n2−α ) · log Φ) where Φ is the spread of the input. This algorithm is used to (2 + )-approximate k-center with the same time complexity.

PDF Details

NeurIPS Conference 2019 Conference Paper

McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds

Rui (Ray) Zhang
Xingwu Liu
Yuyi Wang
Liwei Wang

A crucial assumption in most statistical learning theory is that samples are independently and identically distributed (i. i. d. ). However, for many real applications, the i. i. d. assumption does not hold. We consider learning problems in which examples are dependent and their dependency relation is characterized by a graph. To establish algorithm-dependent generalization theory for learning with non-i. i. d. data, we first prove novel McDiarmid-type concentration inequalities for Lipschitz functions of graph-dependent random variables. We show that concentration relies on the forest complexity of the graph, which characterizes the strength of the dependency. We demonstrate that for many types of dependent data, the forest complexity is small and thus implies good concentration. Based on our new inequalities we are able to build stability bounds for learning from graph-dependent data.

PDF Details

TCS Journal 2019 Journal Article

Minimum cost perfect matching with delays for two sources

Yuval Emek
Yaacov Shapiro
Yuyi Wang

We study a version of the online min-cost perfect matching with delays (MPMD) problem recently introduced by Emek et al. (STOC 2016). In this problem, requests arrive in a continuous time online fashion and should be matched to each other. Each request emerges from one out of n sources, with metric inter-source distances. The algorithm is allowed to delay the matching of requests, but with a cost: when matching two requests, it pays the distance between their respective sources and the time each request has waited from its arrival until it was matched. In this paper, we consider the special case of n = 2 sources that captures the essence of the match-or-wait challenge (cf. rent-or-buy). It turns out that even for this degenerate metric space, the problem is far from trivial. Our results include a deterministic 3-competitive online algorithm for this problem, a proof that no deterministic online algorithm can have competitive ratio smaller than 3, and a proof that the same lower bound applies also for the restricted family of memoryless randomized algorithms.

Details DOI

AAAI Conference 2018 Conference Paper

On the ERM Principle With Networked Data

Yuanhong Wang
Yuyi Wang
Xingwu Liu
Juhua Pu

Networked data, in which every training example involves two objects and may share some common objects with others, is used in many machine learning tasks such as learning to rank and link prediction. A challenge of learning from networked examples is that target values are not known for some pairs of objects. In this case, neither the classical i. i. d. assumption nor techniques based on complete U-statistics can be used. Most existing theoretical results of this problem only deal with the classical empirical risk minimization (ERM) principle that always weights every example equally, but this strategy leads to unsatisfactory bounds. We consider general weighted ERM and show new universal risk bounds for this problem. These new bounds naturally deﬁne an optimization problem which leads to appropriate weights for networked examples. Though this optimization problem is not convex in general, we devise a new fully polynomial-time approximation scheme (FPTAS) to solve it.

PDF Details

AAAI Conference 2018 Conference Paper

Relational Marginal Problems: Theory and Estimation

Ondřej Kuželka
Yuyi Wang
Jesse Davis
Steven Schockaert

In the propositional setting, the marginal problem is to ﬁnd a (maximum-entropy) distribution that has some given marginals. We study this problem in a relational setting and make the following contributions. First, we compare two different notions of relational marginals. Second, we show a duality between the resulting relational marginal problems and the maximum likelihood estimation of the parameters of relational models, which generalizes a well-known duality from the propositional setting. Third, by exploiting the relational marginal formulation, we present a statistically sound method to learn the parameters of relational models that will be applied in settings where the number of constants differs between the training and test data. Furthermore, based on a relational generalization of marginal polytopes, we characterize cases where the standard estimators based on feature’s number of true groundings needs to be adjusted and we quantitatively characterize the consequences of these adjustments. Fourth, we prove bounds on expected errors of the estimated parameters, which allows us to lower-bound, among other things, the effective sample size of relational training data.

PDF Details

AAAI Conference 2018 Conference Paper

Teaching a Machine to Read Maps With Deep Reinforcement Learning

Gino Brunner
Oliver Richter
Yuyi Wang
Roger Wattenhofer

The ability to use a 2D map to navigate a complex 3D environment is quite remarkable, and even difﬁcult for many humans. Localization and navigation is also an important problem in domains such as robotics, and has recently become a focus of the deep reinforcement learning community. In this paper we teach a reinforcement learning agent to read a map in order to ﬁnd the shortest way out of a random maze it has never seen before. Our system combines several state-of-theart methods such as A3C and incorporates novel elements such as a recurrent localization cell. Our agent learns to localize itself based on 3D ﬁrst person images and an approximate orientation angle. The agent generalizes well to bigger mazes, showing that it learned useful localization and navigation capabilities.

PDF Details

IJCAI Conference 2016 Conference Paper

Bounds for Learning from Evolutionary-Related Data in the Realizable Case

Ondřej Kuželka
Yuyi Wang
Jan Ramon

This paper deals with the generalization ability of classifiers trained from non-iid evolutionary-related data in which all training and testing examples correspond to leaves of a phylogenetic tree. For the realizable case, we prove PAC-type upper and lower bounds based on symmetries and matchings in such trees.

PDF Details