Tony Tan
Lecturer
School of Computer Science and Informatics
University of Liverpool
Liverpool, England, UK

Room: George Holt Building, Room 2.16
Email: tonytan@liverpool.ac.uk

Office hour: Drop by my office or make an appointment via email

Teaching: COMP 702 (MSc dissertations co-ordinator), COMP 221 (Planning your career)

Research:

• Succinct SAT and DQBF and applications
• Logic in computer science and applications
• The github account for codes and papers on DQBF: https://github.com/Sat-DQBF

Recent publications: (For full list or dblp list)

• Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
  Chia-Hsuan Lu, Tony Tan and Michael Benedikt
  To appear in the proceedings of TACAS 2026
  https://arxiv.org/abs/2510.18591
  https://zenodo.org/records/17485304

• Model Counting for Dependency Quantified Boolean Formulas (pdf)
  Long-Hin Fung, Che Cheng, Jie-Hong Roland Jiang, Friedrich Slivovsky, Tony Tan
  To appear in the proceedings of AAAI 2026
  https://arxiv.org/abs/2511.07337
  https://github.com/Sat-DQBF/sharp2DQR

• Analysis of logics with arithmetic
  Michael Benedikt, Chia-Hsuan Lu, Tony Tan
  To appear in the proceedings of CSL 2026
  https://arxiv.org/abs/2508.03574

• Decidability of Graph Neural Networks via Logical Characterizations
  Michael Benedikt, Chia-Hsuan Lu, Boris Motik, Tony Tan
  Proceedings of ICALP 2024
  Accepted with minor revision in ACM TOCL
  https://arxiv.org/abs/2404.18151

• Fine-Grained Complexity Analysis of Dependency Quantified Boolean Formulas (pdf)
  Che Cheng, Long-Hin Fung, Jie-Hong Roland Jiang, Friedrich Slivovsky, Tony Tan
  Proceedings of SAT 2025
  Invited to Journal of AI and Journal of AI Research
  Submitted to Journal of AI Research

• Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
  Louwe Kuijer, Tony Tan, Frank Wolter, Michael Zakharyaschev
  Proceedings of LICS 2025 (an extended abstract also appears in DL 2024)
  https://arxiv.org/abs/2504.20491

• Two Variable Logic with Ultimately Periodic Counting (pdf)
  Michael Benedikt, Egor Kostylev, Tony Tan
  SIAM Journal on Computing 53(4): 884--968 (2024)
  The preliminary version appears in the Proceedings of ICALP 2020

• 2-DQBF Solving and Certification via Property-Directed Reachability Analysis (pdf)
  Long-Hin Fung, Che Cheng, Yu-Wei Fan, Tony Tan, Jie-Hong Roland Jiang
  Proceedings of FMCAD 2024 (best paper award)
  Invited and submitted to Formal Methods in System Designs
  https://github.com/Sat-DQBF/2DQR-using-ABC

• On two-variable guarded fragment logic with expressive local Presburger constraints (pdf)
  Chia-Hsuan Lu, Tony Tan
  Logical Methods in Computer Science 20(3) (2024)
  https://arxiv.org/abs/2206.13731

• On the Complexity of k-DQBF (pdf)
  Long-Hin Fung, Tony Tan
  Proceedings of SAT 2023

• Reducing NEXP-complete problems to DQBF
  Fa-Hsun Chen, Shen-Chang Huang, Yu-Cheng Lu, Tony Tan
  Proceedings of FMCAD 2022
  https://arxiv.org/abs/2208.06014

• On Classical Decidable Logics Extended with Percentage Quantifiers and Arithmetics
  Bartosz Bednarczyk, Maja Orlowska, Anna Pacanowska, Tony Tan
  Proceedings of FSTTCS 2021
  https://arxiv.org/abs/2106.15250

• Towards a more efficient approach for the satisfiability of two-variable logic
  Ting-Wei Lin, Chia-Hsuan Lu, Tony Tan
  Proceedings of LICS 2021
  https://arxiv.org/abs/2104.10621

(End of page)