Tony Tan
Senior 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

I am always on the look out for motivated PhD students.

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

Grants:

• Adopting SAT strategy and technology in DQBF setting
  Royal Society
  March 2024 - September 2026

• Lifting SAT technology to DQBF and its applications
  UKRI Engineering and Physical Sciences Research Council (EPSRC)
  September 2026 - August 2029

Recent publications: (For full list or dblp list)

• Decidability of Graph Neural Networks via Logical Characterizations
  Michael Benedikt, Chia-Hsuan Lu, Tony Tan
  ACM Transactions on Computational Logic 2026, issue 2, no. 13, pages 1–65.
  Preliminary version in the Proceedings of ICALP 2024
  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
  To appear in Journal of AI Research
  Preliminary version in the Proceedings of SAT 2025

• Artificial Incorrectness: SMT and LLMs in Hardware Synthesis
  Edward Wang, Joe Walston, Luca Daniel, Tony Tan, Yoni Zohar, Clark Barrett
  Proceedings of NFM 2026

• Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
  Chia-Hsuan Lu, Tony Tan and Michael Benedikt
  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
  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
  Proceedings of CSL 2026
  https://arxiv.org/abs/2508.03574

• 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

(End of page)