
Research Fellow  Lu, ChiJen 





Publications 

1. 
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. 
2. 
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. 
3. 
ChaoKai Chiang, ChiaJung Lee, and ChiJen Lu, "Beating bandits in gradually evolving worlds," Proceedings of the 26th Conference on Learning Theory (COLT), June 2013. 
4. 
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. 
5. 
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. 
6. 
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. 
7. 
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. 
8. 
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. 
9. 
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. 
10. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "Complexity of hardcore set proofs," Computational Complexity, volume 20, number 1, pages 145 – 171, 2011. 
11. 
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. 
12. 
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. 
13. 
ChaoKai Chiang and ChiJen Lu, "Online Learning with Queries," Proceedings of the 21st ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 616629, January 2010. 
14. 
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. 
15. 
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. 
16. 
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. 
17. 
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. 
18. 
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. 
19. 
ChiJen Lu, "On the security loss in cryptographic reductions," Advances in Cryptology  EUROCRYPT, pages 7287, 2009. 
20. 
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. 
21. 
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. 
22. 
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. 
23. 
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. 
24. 
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. 
25. 
ChiJen Lu, ShiChun Tsai, and HsinLung Wu, "Improved hardness amplification in NP," Theoretical Computer Science, volume 370, number 13, pages 293298, 2007. 
26. 
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. 
27. 
ChiJen Lu, "On the complexity of parallel hardness amplification for oneway functions," Proceedings of the 3rd Theory of Cryptography Conference (TCC), pages 462481, 2006. 
28. 
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. 
29. 
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. 
30. 
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. 
31. 
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. 
32. 
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. 
33. 
YanCheng Chang and ChiJen Lu, "Oblivious polynomial evaluation and oblivious neural learning," Theoretical Computer Science, volume 341, number 13, pages 3954, 2005. 
34. 
ChiJen Lu, "Deterministic Hypergraph Coloring and its Applications," SIAM Journal on Discrete Mathematics, volume 18, number 2, pages 320331, 2004. 
35. 
ChiJen Lu, "Encryption against StorageBounded Adversaries from Online Strong Extractors," Journal of Cryptology, volume 17, number 1, pages 2742, 2004. 
36. 
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. 
37. 
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. 
38. 
ChiJen Lu, "HyperEncryption against SpaceBounded Adversaries from Online Strong Extractors," Advances in Cryptology  CRYPTO, pages 257271, August 2002. 
39. 
YanCheng Chang, ChunYun Hsiao, ChiJen Lu, "On the Impossibilities of Basing OneWay Permutations on Central Cryptographic Primitives," Advances in Cryptology  ASIACRYPT, pages 110124, 2002. 
40. 
ChiJen Lu, "Improved Pseudorandom Generators for Combinatorial Rectangles," Combinatorica, volume 22, number 3, pages 417434, 2002. 
41. 
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. 
42. 
ChiJen Lu, "Derandomizing ArthurMerlin Games under Uniform Assumptions," Computational Complexity, volume 10, number 3, pages 247259, 2001. 
43. 
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. 
44. 
ChiJen Lu, "An Exact Characterization of Symmetric Functions in qAC^0[2]," Theoretical Computer Science, volume 261, number 2, pages 297303, 2001. 
45. 
YanCheng Chang and ChiJen Lu, "Oblivious Polynomial Evaluation and Oblivious Neural Learning," Advances in Cryptology  ASIACRYPT 2001, pages 369384, 2001. 
46. 
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. 
47. 
ChiJen Lu, "Derandomizing ArthurMerlin Games under Uniform Assumptions.," the 11th Annual International Symposium on Algorithms And Computation (ISAAC), pages 302312, 2000. 
48. 
David A. Mix Barrington, ChiJen Lu, Peter Bro Miltersen, and Sven Skyum, "On Monotone Plannar Circuits," IEEE Conf on Computational Complexity, pages 2431, 1999. 
49. 
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. 
50. 
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. 
51. 
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. 
52. 
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. 
53. 
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. 











