Research outputs
2025
Fine-Grained Complexity Analysis of Dependency Quantified Boolean Formulas
Cheng, C., Fung, L. H., Jiang, J. H. R., Slivovsky, F., & Tan, T. (2025). Fine-Grained Complexity Analysis of Dependency Quantified Boolean Formulas. In Leibniz International Proceedings in Informatics Lipics Vol. 341. doi:10.4230/LIPIcs.SAT.2025.10
Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
Kuijer, L., Tan, T., Wolter, F., & Zakharyaschev, M. (2025). Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting. In 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (pp. 329-343). IEEE. doi:10.1109/lics65433.2025.00032
2024
Decidability of Graph Neural Networks via Logical Characterizations
Benedikt, M., Lu, C. H., Motik, B., & Tan, T. (2024). Decidability of Graph Neural Networks via Logical Characterizations. In Leibniz International Proceedings in Informatics Lipics Vol. 297. doi:10.4230/LIPIcs.ICALP.2024.127
2-DQBF Solving and Certification via Property-Directed Reachability Analysis
Fung, L. H., Cheng, C., Fan, Y. W., Tan, T., & Jiang, J. H. R. (2024). 2-DQBF Solving and Certification via Property-Directed Reachability Analysis. In Formal Methods in Computer Aided Design Fmcad (pp. 197-207). doi:10.34727/2024/isbn.978-3-85448-065-5_25
ON TWO-VARIABLE GUARDED FRAGMENT LOGIC WITH EXPRESSIVE LOCAL PRESBURGER CONSTRAINTS
Lu, C. -H., & Tan, T. (2024). ON TWO-VARIABLE GUARDED FRAGMENT LOGIC WITH EXPRESSIVE LOCAL PRESBURGER CONSTRAINTS. LOGICAL METHODS IN COMPUTER SCIENCE, 20(3). doi:10.46298/LMCS-20(3:16)2024
Separating Counting from Non-Counting in Fragments of Two-Variable First-Order Logic (Extended Abstract)
Kuijer, L., Tan, T., Wolter, F., & Zakharyaschev, M. (2024). Separating Counting from Non-Counting in Fragments of Two-Variable First-Order Logic (Extended Abstract). In Ceur Workshop Proceedings Vol. 3739.
Two Variable Logic with Ultimately Periodic Counting
Benedikt, M., Kostylev, E. V., & Tan, T. (2024). Two Variable Logic with Ultimately Periodic Counting. SIAM Journal on Computing, 53(4), 884-968. doi:10.1137/22m1504792
2023
On the complexity of k-DQBF
Tan, T., & Fung, L. -H. (2023). On the complexity of k-DQBF. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). doi:10.4230/LIPIcs.SAT.2023.10
2022
Reducing NEXP-complete problems to DQBF
Chen, F. -H., Huang, S. -C., Lu, Y. -C., & Tan, T. (2022). Reducing NEXP-complete problems to DQBF. In 2022 FORMAL METHODS IN COMPUTER-AIDED DESIGN, FMCAD (pp. 199-204). doi:10.34727/2022/isbn.978-3-85448-053-2_26
2021
Towards a more efficient approach for the satisfiability of two-variable logic
Lin, T. -W., Lu, C. -H., & Tan, T. (2021). Towards a more efficient approach for the satisfiability of two-variable logic. In 2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS). doi:10.1109/LICS52264.2021.9470502
2020
Two Variable Logic with Ultimately Periodic Counting.
Benedikt, M., Kostylev, E. V., & Tan, T. (2020). Two Variable Logic with Ultimately Periodic Counting.. In A. Czumaj, A. Dawar, & E. Merelli (Eds.), ICALP Vol. 168 (pp. 112:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-138-2
2015
On the Variable Hierarchy of First-Order Spectra
Kopczynski, E., & Tan, T. (2015). On the Variable Hierarchy of First-Order Spectra. ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 16(2). doi:10.1145/2733376
REGULAR GRAPHS AND THE SPECTRA OF TWO-VARIABLE LOGIC WITH COUNTING
Kopczynski, E., & Tan, T. (2015). REGULAR GRAPHS AND THE SPECTRA OF TWO-VARIABLE LOGIC WITH COUNTING. SIAM JOURNAL ON COMPUTING, 44(3), 786-818. doi:10.1137/130943625