
Research Fellow/Professor  Lu, ChiJen 





Publications 

1. 
RuoChun Tzeng, PoAn Wang, Alexandre Proutiere, and ChiJen Lu, "Closing the ComputationalStatistical Gap in Best Arm Identification for Combinatorial Semibandits," Thirtyseventh Conference on Neural Information Processing Systems (NeurIPS), December 2023. 
2. 
RuoChun Tzeng, PoAn Wang, Florian Adriaens, Aristides Gionis, and ChiJen Lu, "Improved analysis of randomized SVD for topeigenvector approximation," International Conference on Artificial Intelligence and Statistics, AISTATS 2022, pages 20452072, March 2022. 
3. 
PoAn Chen, ChiJen Lu, and YuSin Lu, "An alternating algorithm for finding linear ArrowDebreu market equilibria," Theory of Computing Systems, volume 66, number 1, pages 3855, 2022. 
4. 
TingYun Chang, ChiJen Lu, "Rethinking Why IntermediateTask FineTuning Works," Findings of the Association for Computational Linguistics: EMNLP 2021, pages 706713, November 2021. 
5. 
ChuangChieh Lin, ChiJen Lu, and PoAn Chen, "How good is a twoparty election game?," Theoretical Computer Science, volume 871, pages 7993, 2021. 
6. 
TingYun Chang and ChiJen Lu, "TinyGAN: Distilling BigGAN for conditional image generation," 15th Asian Conference on Computer Vision (ACCV), Lecture Notes in Computer Science, December 2020. 
7. 
HongYou Chen and ChiJen Lu, "Nested variance estimating VAE/GAN for face generation," Proceedings of the 2019 International Joint Conference on Neural Networks (IJCNN), July 2019. 
8. 
YiShan Wu, PoAn Wang, and ChiJen Lu, "Lifelong optimization with low regret," Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), April 2019. 
9. 
JunKun Wang, ChiJen Lu, and ShouDe Lin, "Online linear optimization with sparsity constraints," Proceedings of the 30th International Conference on Algorithmic Learning Theory (ALT), March 2019. 
10. 
ChiNing Chou, KaiMin Chung and ChiJen Lu, "On the Algorithmic Power of Spiking Neural Networks," The 10th Innovations in Theoretical Computer Science (ITCS 2019), January 2019. 
11. 
JenHou Chou and ChiJen Lu, "The communication complexity of graphical games on grid graphs," Proceedings of the 14th Conference on Web and Internet Economics 14th Conference on Web and Internet Economics (WINE), December 2018. 
12. 
ChuangChieh Lin and ChiJen Lu, "Efficient mechanisms for peer grading and dueling bandits," Proceedings of the 10th Asian Conference on Machine Learning (ACML), November 2018. 
13. 
ChenYu Wei, YiTe Hong, and ChiJen Lu, "Online Reinforcement Learning in Stochastic Games," Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), December 2017. 
14. 
PoAn Wang and ChiJen Lu, "Tensor Decomposition via Simultaneous Power Iteration," Proceedings of the 34st International Conference on Machine Learning (ICML), August 2017. 
15. 
PoAn Chen and ChiJen Lu, "Generalized mirror descents in congestion games," Artificial Intelligence, volume 241, pages 217243, December 2016. 
16. 
ChenYu Wei, YiTe Hong, and ChiJen Lu, "Tracking the Best Expert in Nonstationary Stochastic Environments," Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), December 2016. 
17. 
PoAn Chen, YiLe Chen, and ChiJen Lu, "Bounds on the Price of Anarchy for a More General Class of Directed Graphs in Opinion Formation Games," Operations Research Letters, volume 44, number 6, pages 808811, November 2016. 
18. 
ChunLiang Li, HsuanTien Lin, and ChiJen Lu, "Rivalry of Two Families of Algorithms for MemoryRestricted Streaming PCA," Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS),, May 2016. 
19. 
PoAn Chen, YiLe Chen, and ChiJen Lu, "How Much of a Person Influencing the Others and Being Influenced Matters in Opinion Formation Games," Collective Intelligence Conference, May 2016. 
20. 
YiTe Hong and ChiJen Lu, "Online Learning in Markov Decision Processes with continuous actions," Proceedings of the 26th International Conference on Algorithmic Learning Theory (ALT), Lecture Notes in Artificial Intelligence, October 2015. 
21. 
PoAn Chen and ChiJen Lu, "Playing congestion games with bandit feedback," Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2015. 
22. 
KuChun Chou, ChaoKai Chiang, HsuanTien Lin, and ChiJen Lu, "Pseudoreward algorithms for contextual bandits with linear payoff functions," Proceedings of the Asian Conference on Machine Learning (ACML), November 2014. 
23. 
ShangTse Chen, HsuanTien Lin, and ChiJen Lu, "Boosting with online binary learners for the multiclass bandit problem," Proceedings of the 31st International Conference on Machine Learning (ICML), June 2014. 
24. 
PoAn Chen and ChiJen Lu, "Generalized mirror descents in congestion games with splittable flows," Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2014. 
25. 
ChaoKai Chiang, ChiaJung Lee, and ChiJen Lu, "Beating bandits in gradually evolving worlds," Proceedings of the 26th Conference on Learning Theory (COLT), June 2013. 
26. 
JenHou Chou, ChiJen Lu, and MuEn Wu, "Making profit in a prediction market," Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, August 2012. 
27. 
ChaoKai Chiang, Tianbao Yang, ChiaJung Lee, Mehrdad Mahdavi, ChiJen Lu, Rong Jin and Shenghuo Zhu, "Online optimization with gradual variations," Proceedings of the 25th Conference on Learning Theory (COLT), June 2012. 
28. 
ShangTse Chen, HsuanTien Lin, and ChiJen Lu, "An online boosting algorithm with theoretical justifications," Proceedings of the 29th International Conference on Machine Learning (ICML), June 2012. 
29. 
ChiJen Lu, "Hitting set generators for sparse polynomials over any finite fields," Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC), June 2012. 
30. 
ChiaJung Lee, ChiJen Lu and ShiChun Tsai, "Extracting computational entropy and learning noisy linear functions," IEEE Transactions on Information Theory, volume 57, number 8, pages 54855496, 2011. 
31. 
ChiJen Lu and WeiFu Lu, "Making online decisions with bounded memory," Proceedings of the 22nd International Conference on Algorithmic Learning Theory (ALT), Lecture Notes in Artificial Intelligence, pages 249261, 2011. 
32. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "Complexity of hardcore set proofs," Computational Complexity, volume 20, number 1, pages 145 – 171, 2011. 
33. 
ChiaJung Lee, ChiJen Lu, and ShiChun Tsai, "Computational randomness from generalized hardcore sets," Proceedings of the 20th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science, pages 7889, 2011. 
34. 
Fu Chang, ChienYang Guo, XiaoRong Lin, and ChiJen Lu, "Tree decomposition for largescale SVM Problems," Journal of Machine Learning Research, volume 11, pages 2935−2972, October 2010. 
35. 
ChaoKai Chiang and ChiJen Lu, "Online Learning with Queries," Proceedings of the 21st ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 616629, January 2010. 
36. 
KaiMin Chung, FengHao Liu, ChiJen Lu, and BoYin Yang, "Efficient stringcommitment from weak bitcommitment and fullspectrum amplification theorem for puzzles," Advances in Cryptology  ASIACRYPT, Lecture Notes in Computer Science, pages 268282, 2010. 
37. 
JenHou Chou and ChiJen Lu, "Communication requirements for stable marriages," Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science, pages 371382, 2010. 
38. 
ChiJen Lu and HsinLung Wu, "On the hardness against constantdepth linearsize circuits," Discrete Mathematics, Algorithms and Applications, volume 2, number 4, pages 515 – 526, 2010. 
39. 
ChiaJung Lee, ChiJen Lu, and ShiChun Tsai, "Deterministic extractors for independentsymbol sources," IEEE Transactions on Information Theory, volume 56, number 12, pages 6501 – 6512, 2010. 
40. 
ChiJen Lu and HsinLung Wu, "On the hardness against constantdepth linearsize circuits," Proceedings of the 16th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, pages 1322, 2010. 
41. 
ChiYuan Chan, ShanChyun Ku, ChiJen Lu, and BiingFeng Wang, "Efficient algorithms for two generalized 2median problems and the group median problem on trees," Theoretical Computer Science, volume 410, number 810, pages 867876, 2009. 
42. 
ChiJen Lu, "On the security loss in cryptographic reductions," Advances in Cryptology  EUROCRYPT, pages 7287, 2009. 
43. 
ChiaJung Lee, ChiJen Lu and ShiChun Tsai, "Extracting computational entropy and learning noisy linear functions," Proceedings of the 15th International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, pages 338347, 2009. 
44. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "On the complexity of hardness amplification," IEEE Transactions on Information Theory, volume 54, number 10, pages 45754586, October 2008. 
45. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "On the complexity of hardcore set constructions," Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pages 183194, 2007. 
46. 
ChunYuan Hsiao and ChiJen Lu and Leonid Reyzin, "Conditional computational entropy, or toward separating pseudoentropy from compressibility," Advances in Cryptology  EUROCRYPT, Lecture Notes in Computer Science, 2007. 
47. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "Impossibility results on weakly blackbox hardness amplification," Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT),, Lecture Notes in Computer Science, 2007. 
48. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "Improved hardness amplification in NP," Theoretical Computer Science, volume 370, number 13, pages 293298, 2007. 
49. 
ChiaJung Lee, ChiJen Lu, and ShiChun Tsai, "Deterministic extractors for independentsymbol sources," In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), pages 8495, 2006. 
50. 
ChiJen Lu, "On the complexity of parallel hardness amplification for oneway functions," Proceedings of the 3rd Theory of Cryptography Conference (TCC), pages 462481, 2006. 
51. 
YanCheng Chang, ChunYun Hsiao, and ChiJen Lu, "The impossibility of basing oneway permutations on central cryptographic primitives," Journal of Cryptology, volume 19, number 1, pages 97114, 2006. 
52. 
Fu Chang, ChinChin Lin, and ChiJen Lu, "Adaptive prototype learning algorithms: theoretical and experimental studies," Journal of Machine Learning Research, volume 7(Oct), pages pp. 21252148, 2006. 
53. 
YanCheng Chang and ChiJen Lu, "Oblivious polynomial evaluation and oblivious neural learning," Theoretical Computer Science, volume 341, number 13, pages 3954, 2005. 
54. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "On the Complexity of Hardness Amplification," Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC), pages 170182, 2005. 
55. 
ChiaJung Lee, ChiJen Lu, ShiChun Tsai, and WenGuey Tzeng, "Extracting randomness from multiple independent sources," IEEE Transactions on Information Theory, volume 51, number 6, pages 22242227, 2005. 
56. 
ChiJen Lu, "Deterministic Hypergraph Coloring and its Applications," SIAM Journal on Discrete Mathematics, volume 18, number 2, pages 320331, 2004. 
57. 
ChiJen Lu, "Encryption against StorageBounded Adversaries from Online Strong Extractors," Journal of Cryptology, volume 17, number 1, pages 2742, 2004. 
58. 
Fu Chang, ChunJen Chen, and ChiJen Lu, "A lineartime componentlabeling algorithm using contour tracing technique," Computer Vision and Image Understanding, volume 93, number 2, pages 206220, 2004. 
59. 
ChiJen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson, "Extractors: Optimal up to Constant Factors," Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pages 602611, 2003. 
60. 
ChiJen Lu, "HyperEncryption against SpaceBounded Adversaries from Online Strong Extractors," Advances in Cryptology  CRYPTO, pages 257271, August 2002. 
61. 
YanCheng Chang, ChunYun Hsiao, ChiJen Lu, "On the Impossibilities of Basing OneWay Permutations on Central Cryptographic Primitives," Advances in Cryptology  ASIACRYPT, pages 110124, 2002. 
62. 
ChiJen Lu, "Improved Pseudorandom Generators for Combinatorial Rectangles," Combinatorica, volume 22, number 3, pages 417434, 2002. 
63. 
ChiJen Lu, "An Exact Characterization of Symmetric Functions in qAC^0[2]," Theoretical Computer Science, volume 261, number 2, pages 297303, 2001. 
64. 
YanCheng Chang and ChiJen Lu, "Oblivious Polynomial Evaluation and Oblivious Neural Learning," Advances in Cryptology  ASIACRYPT 2001, pages 369384, 2001. 
65. 
ShanChyun Ku, ChiJen Lu, BiingFeng Wang, and TzuChin Lin, "Efficient Algorithms for Two Generalized 2Median Problems on Trees," Proceedings of the 12th Annual International Symposium on Algorithms And Computation (ISAAC), pages 768778, 2001. 
66. 
ChiJen Lu, "Derandomizing ArthurMerlin Games under Uniform Assumptions," Computational Complexity, volume 10, number 3, pages 247259, 2001. 
67. 
Tom Leighton, ChiJen Lu, Satish Rao, and Aravind Srinivasan, "New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning," SIAM Journal on Computing, volume 31, number 2, pages 626641, 2001. 
68. 
ChiJen Lu and ShiChun Tsai, "A Note on Iterating an alphaary Gray Code," SIAM Journal on Discrete Mathematics, volume 14, number 2, pages 237239, 2001. 
69. 
ChiJen Lu, "Derandomizing ArthurMerlin Games under Uniform Assumptions.," the 11th Annual International Symposium on Algorithms And Computation (ISAAC), pages 302312, 2000. 
70. 
David A. Mix Barrington, ChiJen Lu, Peter Bro Miltersen, and Sven Skyum, "On Monotone Plannar Circuits," IEEE Conf on Computational Complexity, pages 2431, 1999. 
71. 
ChiJen Lu, "A deterministic approximation algorithm for a minmax integer programming problem," Proceedings of the 10th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 663668, 1999. 
72. 
ChiJen Lu, "Improved pseudorandom generators for combinatorial rectangles," Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, pages 223234, 1998. 
73. 
ChiJen Lu, "Deterministic hypergraph coloring and its applications," Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Lecture Notes in Computer Science, pages 3546, 1998. 
74. 
Dave Mix Barrington, ChiJen Lu, Peter Bro Miltersen, and Sven Skyum, "Searching Constant Width Mazes Captures the AC0Hierarchy," Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 7383, 1998. 
75. 
ChiJen Lu, "An exact characterization of symmetric functions in qAC^0[2]," Proceedings of the 4th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, pages 167173, 1998. 











