UTS site search

UTS:QSI has one paper accepted at FOCS 2017

5 August 2017

Senior Lecturer Dr Youming Qiao and PhD student Yinan Li had their paper titled “Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model” accepted for publication in the Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS 2017). FOCS is consistently ranked as one of the top two conferences for theoretical computer science and algorithms in the world. Their paper shows that one can apply techniques from graph isomorphism problem to make progress on a hard-core instance of group isomorphism problem. A main result is based on an average analysis done in a linear algebraic version of the celebrated Erdős-Rényi model of random graphs. This paper will be presented during the conference, which will be held at the Simons Institute of the University of California, Berkeley, from October 15th to 17th, 2017. Dr Youming Qiao’s research that leads to this paper is supported by a Discovery Early Career Researcher Award (DECRA) from the Australian Research Council. Also noteworthy is that Mr Yinan Li would be the first UTS-based student co-authored a FOCS paper.