Austen Z. Fan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Austen Z. Fan has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Paraschos Koutris
University of Wisconsin-Madison, Madison, USA
7 shared publications - Jin-Yi Cai
University of Wisconsin-Madison, Madison, USA
6 shared publications - Hangdong Zhao
University of Wisconsin-Madison, Madison, WI, USA
5 shared publications Jin-Yi Cai
Department of Computer Sciences University of Wisconsin
5 shared publications- Andrzej Kaczmarczyk
University of Chicago
2 shared publications - Niclas Boehmer
Hasso Plattner Institute University of Potsdam Germany
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 967-978
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 967-978
Open AccessNew Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
- Open Access
- 27 March 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (3) , 1-42
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this article, we study the complexity of evaluating Conjunctive Queries with negation ( \(\mathsf {CQ}^{\lnot }\) ). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation ( \(\mathsf {FAQ}^{\lnot }\) ). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.- 27 March 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (3) , 1-42
Open AccessConjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this article, we study the complexity of evaluating Conjunctive Queries with negation ( \(\mathsf {CQ}^{\lnot }\) ). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation ( \(\mathsf {FAQ}^{\lnot }\) ). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs. - Open Access
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) \#P-hard for general graphs but computable in P-time for planar graphs, or (3) \#P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.Open AccessNew Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) \#P-hard for general graphs but computable in P-time for planar graphs, or (3) \#P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields. - Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-22
Circuits and Formulas for Datalog over Semirings
In this paper, we study circuits and formulas for provenance polynomials of Datalog programs. We ask the following question: given an absorptive semiring and a fact of a Datalog program, what is the optimal depth and size of a circuit/formula that computes its provenance polynomial? We focus on absorptive semirings as these guarantee the existence of a polynomial-size circuit. Our main result is a dichotomy for several classes of Datalog programs on whether they admit a formula of polynomial size or not. We achieve this result by showing that for these Datalog programs the optimal circuit depth is either Θ(log m ) or Θ(log 2 m ), where m is the input size. We also show that for Datalog programs with the polynomial fringe property, we can always construct low-depth circuits of size O(log 2 m ). Finally, we give characterizations of when Datalog programs are bounded over more general semirings.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-22
Open AccessCircuits and Formulas for Datalog over Semirings
In this paper, we study circuits and formulas for provenance polynomials of Datalog programs. We ask the following question: given an absorptive semiring and a fact of a Datalog program, what is the optimal depth and size of a circuit/formula that computes its provenance polynomial? We focus on absorptive semirings as these guarantee the existence of a polynomial-size circuit. Our main result is a dichotomy for several classes of Datalog programs on whether they admit a formula of polynomial size or not. We achieve this result by showing that for these Datalog programs the optimal circuit depth is either Θ(log m ) or Θ(log 2 m ), where m is the input size. We also show that for Datalog programs with the polynomial fringe property, we can always construct low-depth circuits of size O(log 2 m ). Finally, we give characterizations of when Datalog programs are bounded over more general semirings.
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-24
Circuit Bounds for Conjunctive Queries with Self-joins
In this paper, we study circuit size bounds for Conjunctive Queries (CQs) under different semiring semantics. Recent work established tight bounds for self-join-free CQs over the tropical semiring, among other results [16]. Here, we extend these results in two main directions. First, we prove a lower bound for any self-join-free CQ over the Boolean semiring by extending Razborov and Alon-Boppana's classic lower bound result for the k -clique problem [1, 38]. Second, we characterize the circuit complexity of CQs with self-joins by relating them to appropriate self-join free CQs. Interestingly, such correspondence crucially depends on the underlying semiring. To achieve this result, we present a novel technique of investigating the circuit complexity of a CQ with self-joins through the lens of endomorphisms.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-24
Open AccessCircuit Bounds for Conjunctive Queries with Self-joins
In this paper, we study circuit size bounds for Conjunctive Queries (CQs) under different semiring semantics. Recent work established tight bounds for self-join-free CQs over the tropical semiring, among other results [16]. Here, we extend these results in two main directions. First, we prove a lower bound for any self-join-free CQ over the Boolean semiring by extending Razborov and Alon-Boppana's classic lower bound result for the k -clique problem [1, 38]. Second, we characterize the circuit complexity of CQs with self-joins by relating them to appropriate self-join free CQs. Interestingly, such correspondence crucially depends on the underlying semiring. To achieve this result, we present a novel technique of investigating the circuit complexity of a CQ with self-joins through the lens of endomorphisms.
- Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-24
Output-sensitive Conjunctive Query Evaluation
Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of join algorithms have been developed, and commercial database engines use finely tuned join heuristics that take into account many factors including the selectivity of predicates, memory, IO, etc. However, most of the results have catered to either full join queries or non-full join queries but with degree constraints (such as PK-FK relationships) that makes join evaluation easier. Further, most of the algorithms are also not output-sensitive. In this paper, we present a novel, output-sensitive algorithm for the evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free variables. Our result is based on a novel generalization of the Yannakakis algorithm and shows that it is possible to improve the running time guarantee of Yannakakis algorithm by a polynomial factor. Importantly, our algorithmic improvement does not depend on the use of fast matrix multiplication, as a recently proposed algorithm does. The application of our algorithm recovers known prior results and improves on known state-of-the-art results for common queries such as paths and stars. The upper bound is complemented with a matching lower bound for star queries, a restricted subclass of acyclic CQs, and a family of cyclic CQs conditioned on two variants of the k -clique conjecture.
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-24
Open AccessOutput-sensitive Conjunctive Query Evaluation
Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of join algorithms have been developed, and commercial database engines use finely tuned join heuristics that take into account many factors including the selectivity of predicates, memory, IO, etc. However, most of the results have catered to either full join queries or non-full join queries but with degree constraints (such as PK-FK relationships) that makes join evaluation easier. Further, most of the algorithms are also not output-sensitive. In this paper, we present a novel, output-sensitive algorithm for the evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free variables. Our result is based on a novel generalization of the Yannakakis algorithm and shows that it is possible to improve the running time guarantee of Yannakakis algorithm by a polynomial factor. Importantly, our algorithmic improvement does not depend on the use of fast matrix multiplication, as a recently proposed algorithm does. The application of our algorithm recovers known prior results and improves on known state-of-the-art results for common queries such as paths and stars. The upper bound is complemented with a matching lower bound for star queries, a restricted subclass of acyclic CQs, and a family of cyclic CQs conditioned on two variants of the k -clique conjecture.
- Open Access
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-20
Tight Bounds of Circuits for Sum-Product Queries
In this paper, we ask the following question: given a Boolean Conjunctive Query (CQ), what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. Notably, it is shown that any circuit F that computes a CQ over the tropical semiring must have size log |F| ≥ (1-ε) · da-entw for any ε >0, where da-entw is the degree-aware entropic width of the query. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas (i.e., circuits where each gate has outdegree one), and to bounds for non-Boolean CQs.
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-20
Open AccessTight Bounds of Circuits for Sum-Product Queries
In this paper, we ask the following question: given a Boolean Conjunctive Query (CQ), what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. Notably, it is shown that any circuit F that computes a CQ over the tropical semiring must have size log |F| ≥ (1-ε) · da-entw for any ε >0, where da-entw is the degree-aware entropic width of the query. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas (i.e., circuits where each gate has outdegree one), and to bounds for non-Boolean CQs.
- Open Access
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-19
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-19
Open AccessConjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.
- Open Access
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries, but with a slightly increased preprocessing time which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings, but can be removed when the semiring has specific structure. Finally, we show an application of our results to computing the difference of CQs.
Open AccessConjunctive Queries with Negation and Aggregation: A Linear Time Characterization
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries, but with a slightly increased preprocessing time which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings, but can be removed when the semiring has specific structure. Finally, we show an application of our results to computing the difference of CQs.