Fan Wei

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 9, 2026 The recent successes of large language models (LLMs) have led to active lines of work in formal theories of language generation and learning. We build on one such theory, language generation in the limit, in which an adversary enumerates the strings of an ... Full text Cite

Density Measures for Language Generation

Conference Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · January 1, 2025 The recent successes of large language models (LLMs) have led to a surge of theoretical research into the properties of language generation. A recent line of work has proposed an abstract view of the question - called language generation in the limit - in ... Full text Cite

On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs

Conference Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications · 2023 We call a multigraph irregular if it has pairwise distinct vertex degrees. No nontrivial (simple) graph is thus irregular. The irregularity strength of a graph $G$, $s(G)$, is a specific measure of the ``level of irregularity'' of $G$. It might be defin ... Full text Cite

Finding cliques in social networks: A new distribution-free model

Conference Leibniz International Proceedings in Informatics Lipics · July 1, 2018 We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure - the property that pairs of vertices with common neighbors tend to be adjacent. Our most ... Full text Cite

Fast Property Testing and Metrics for Permutations

Conference Combinatorics Probability and Computing · July 1, 2018 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are -far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial o ... Full text Cite

Graph edge partitioning via neighborhood heuristic

Conference Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · August 13, 2017 We consider the edge partitioning problem that partitions the edges of an input graph into multiple balanced components, while minimizing the total number of vertices replicated (one vertex might appear in more than one partition). This problem is critical ... Full text Cite

Local max-cut in smoothed polynomial time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2017 In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continue ... Full text Cite

Self-paced multi-task learning

Conference 31st Aaai Conference on Artificial Intelligence Aaai 2017 · January 1, 2017 Multi-task learning is a paradigm, where multiple tasks are jointly learnt. Previous multi-task learning models usually treat all tasks and instances per task equally during learning. Inspired by the fact that humans often learn from easy concepts to hard ... Cite

Permutation property testing under different metrics with low query complexity

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2017 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial ob ... Full text Cite

Spatially regularized streaming sensor selection

Conference 30th Aaai Conference on Artificial Intelligence Aaai 2016 · January 1, 2016 Sensor selection has become an active topic aimed at energy saving, information overload prevention, and communication cost planning in sensor networks. In many real applications, often the sensors' observation regions have overlaps and thus the sensor net ... Cite