My research interest is theoretical computer science (TCS), and in particular, computational complexity. I am enthralled by problems in circuit complexity, algebraic computation, and quantum computation. In addition, I am also interested in pseudorandomness, cryptography, coding theory, and the interaction of TCS with other fields.
On the Algorithmic Power of Spiking Neural Networks
with Kai-Min Chung, Chi-Jen Lu
Innovations in Theoretical Computer Science (ITCS 2019).
- [arxiv] [conference version] [slides]
Photo by Pennstatenews.
Spiking neural networks (SNNs) are mathematical models for biological neural networks such as our brain. In this work, we study SNNs through the lens of algorithms. In particular, we show that the firing rate of the integrate-and-fire SNN can efficiently solve the non-negative least squares problem and $\ell_1$ minimization problem. Further, our proof gives new interpretations on the integrate-and-fire SNN where the external charging and spiking effects can be viewed as gradient and projection respectively in the dual space.
Personalized Difficulty Adjustment for Countering the Double-Spending Attack in Proof-of-Work Consensus Protocols
with Yu-Jing Lin, Ren Chen, Hsiu-Yao Chang, I-Ping Tu, Shih-wei Liao
IEEE International Conference on Blockchain (Blockchain 2018).
- [arxiv] [conference version]
Hardness vs Randomness for Bounded Depth Arithmetic Circuits
with Mrinal Kumar, Noam Solomon
Computational Complexity Conference (CCC 2018).
- [arxiv] [eccc] [conference version] [slides]
Tracking the $\ell_2$ Norm with Constant Update Time
with Zhixian Lei, Preetum Nakkiran, in submission.
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
with Boaz Barak, Zhixian Lei, Tselil Schramm, Yueqi Sheng, in submission.