Skip to main content

Xuangui Huang

PhD Student

Contact

WPersonal site

Estslxg@ccs.neu.edu

Office Location

440 Huntington Avenue
266 West Village H
Boston, MA 02115

BIOGRAPHY

Xuangui Huang is a PhD student in the Theoretical Computer Science program at Northeastern University’s College of Computer and Information Science, advised by Professor Emanuele Viola. Xuangui is particularly interested in computational complexity. Prior to joining the PhD program at Northeastern, Xuangui researched parameterized complexity, circuit complexity, and descriptive complexity while earning both his Bachelor’s and Master’s of Science from Shanghai Jiao Tong University.

EDUCATION

  • MS, Shanghai Jiao Tong University – China
  • BS, Shanghai Jiao Tong University – China

About Me

  • Hometown: Swatow, China
  • Field of Study: Theoretical Computer Science
  • PhD Advisor: Emanuele Viola

What are your research interests?

Computational complexity.

What’s one problem you’d like to solve with your research/work?

Open problems, small or big.

What aspect of what you do is most interesting?

I am most interested in solving challenging problems with many failures.

What are your research or career goals, going forward?

I want to be a real scientist, more precisely, a real complexity theoretician.

 

Recent Publications

Slicewise definability in first-order logic with bounded quantifier rank

Chen, Yijia, Joerg Flum, and Xuangui Huang. "Slicewise Definability in First-order Logic with Bounded Quantifier Rank." 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017.

Abstract

For every q ∈ N let FOq denote the class of sentences of first-order logic FO of quantifier rank at most q. If a graph property can be defined in FOq, then it can be decided in time O(n q ). Thus, minimizing q has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size k. Usually this can only be expressed by a sentence of quantifier rank at least k. We use the color-coding method to demonstrate that some (hyper)graph problems can be defined in FOq where q is independent of k. This property of a graph problem is equivalent to the question of whether the corresponding parameterized problem is in the class para-AC0 . It is crucial for our results that the FO-sentences have access to built-in addition and multiplication. It is known that then FO corresponds to the circuit complexity class uniform AC0 . We explore the connection between the quantifier rank of FO-sentences and the depth of AC0 -circuits, and prove that FOq ( FOq+1 for structures with built-in addition and multiplication.