1 citations · 2 across the 11 of their papers we have counts for
13 papers
K-Join: Combining Vertex Covers for Parallel Joins
Simon Frisk, Austen Fan, Paraschos Koutris
Significant research effort has been devoted to improving the performance of join processing in the massively parallel computation model, where the goal is to evaluate a query with…
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Austen Fan, Jin-Yi Cai, Shuai Shao +1
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in for the eight-vertex model, the partition func…
Circuits and Formulas for Datalog over Semirings
Austen Z. Fan, Paraschos Koutris, Sudeepa Roy
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 pr…
Output-sensitive Conjunctive Query Evaluation
Shaleen Deep, Hangdong Zhao, Austen Z. Fan +1
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…
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
Hangdong Zhao, Austen Z. Fan, Xiating Ouyang +1
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 en…
Restricted Holant Dichotomy on Domains 3 and 4
Yin Liu, Austen Z. Fan, Jin-Yi Cai
denotes a class of counting problems specified by a constraint function . We prove complexity dichotomy theorems for in…
The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems
Austen Z. Fan, Paraschos Koutris, Hangdong Zhao
We study the fine-grained complexity of evaluating Boolean Conjunctive Queries and their generalization to sum-of-product problems over an arbitrary semiring. For these problems, w…
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy
Jin-Yi Cai, Austen Z. Fan
We prove a complexity dichotomy theorem for a class of Holant problems on planar 3-regular bipartite graphs. The complexity dichotomy states that for every weighted constraint func…
Properties of Position Matrices and Their Elections
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski +4
We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix).…
Certifiable Robustness for Nearest Neighbor Classifiers
Austen Z. Fan, Paraschos Koutris
ML models are typically trained using large datasets of high quality. However, training datasets often contain inconsistent or incomplete data. To tackle this issue, one solution i…
Bipartite 3-Regular Counting Problems with Mixed Signs
Jin-Yi Cai, Austen Z. Fan, Yin Liu
We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid…
A Prioritized Trajectory Planning Algorithm for Connected and Automated Vehicle Mandatory Lane Changes
Nachuan Li, Austen Z. Fan, Riley Fischer +2
We introduce a prioritized system-optimal algorithm for mandatory lane change (MLC) behavior of connected and automated vehicles (CAV) from a dedicated lane. Our approach applies a…
Dichotomy Result on 3-Regular Bipartite Non-negative Functions
Austen Z. Fan, Jin-Yi Cai
We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function $f = [x_…