Publications


  2009 2008 2007
  2006 2005 2004


2009
  Authors Title Journal/Meeting Date
1 Peng-Jun Wan, Chih-Wei Yi, Lixin Wang, Frances Yao, and Xiaohua Jia Asymptotic Critical Transmission Radii for Greedy
Forward Routing in Wireless Ad Hoc Networks		 IEEE TRANSACTIONS ON COMMUNICATIONS 2009
2 Changcun Ma, Donghyun Kim, Yuexuan Wang, Wei Wang, Nassim Sohaee and Weili Wu Hardness of k-Vertex Connected Subgraph Augmentation Problem Journal of Combinatorial Optimization (JOCO) 2009
3 Changyuan Yu Truthful mechanisms for two-range-values variant of unrelated scheduling Theoretical Computer Science 2009
4 Jun Guo, YuexuanWang, Suogang Gao, Jiangchen Yu, WeiliWu Constructing error-correcting pooling designs with symplectic space Journal of Combinatorial Optimization (JOCO) 2009
5 Andrew C.C. Yao, Frances F. Yao, Yunlei Zhao

A Note on the Feasibility of Generalized Universal Composability

 Mathematical Structure in Computer Science 2009
6 ZHIQIANG ZHANG, YAOYUN SHI

COMMUNICATION COMPLEXITIES OF SYMMETRIC XOR FUNCTIONS

 Quantum Information and Computation 2009
7 XIAOFENG GAO, YUEXUAN WANG, XIANYUE LI, WEILI WU

ANALYSIS ON THEORETICAL BOUNDS FOR
APPROXIMATING DOMINATING SET PROBLEMS

 Discrete Mathematics, Algorithms and Applications 2009
8 Hong-Bin Chen, Yongxi Cheng, Qian He, and Chongchong Zhong Transforming an Error-Tolerant Separable Matrix to an Error-Tolerant Disjunct Matrix Discrete Applied Mathematics 2009
9 Xi Chen and Xiaotie Deng

A Simplicial Approach for Discrete Fixed Point Theorems

 Algorithmica 2009
10 Decheng Dai,Changyuan YU

A5+ε-Approximation Algorithm for Minimum Weighted Dominating Set in Unit Disk Graph

 Theoretical Computer Science 2009
11 Jing Xiao,Lan Liu,Lirong Xia,Tao Jiang

Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant linear Equations

 SIAM Journal on Computing 2009
12 Andrew C.C. Yao, Frances F. Yao, Yunlei Zhao

A Note on Universal Composable Zero Knowledge in Common Reference String Model

 Theoretical Computer Science 2009
13 Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu,  Francis C.M. Lau

Set Multi-Covering via Inclusion-Exclusion

 Theoretical Computer Science 2009
14 Yuexuan Wang, Yin Jie,  Meizhi Hu

A Scheduling Method for Service Chain in Equipment Grid

 SERVICES-I 2009
15 Feng Zou; Yuexuan Wang; Xiao-Hua Xu; Xianyue Li; Hongwei Du; Pengjun Wan;Weili Wu

New Approximations for Minimum-Weighted Dominating Set and Minimum-Weighted Connected Dominating Set on Unit Disk Graphs

 Theoretical Computer Science 2009
16 Deying Li; Yuexuan Wang; Qinghua Zhu; Huiqiang Yang

k-inconnected Many-to-One Routing in Wireless Networks

 Theoretical Computer Science 2009
17 Xiaoming Sun, Andrew Chi-Chih Yao

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

 Algorithmica 2009
18 WEIWEI LANG, YUEXUAN WANG, JAMES YU, SUOGANG GAO, WEILI WU

ERROR-TOLERANT TRIVIAL TWO-STAGE GROUP
TESTING FOR COMPLEXES USING ALMOST
SEPARABLE AND ALMOST DISJUNCT MATRICES

 Discrete Mathematics, Algorithms and Applications 2009

 

 

 

2008
  Authors Title Journal/Meeting Date
1 Yongxi Cheng and Ding-Zhu Du New constructions of one and two stage pooling designs Journal of Computational Biology 15(2), 2008, 195-205 2008
2 Yongxi Cheng A New Class of Antimagic Cartesian Product Graphs Discrete Mathematics 2008
3 Jing Zhang, Xin Gao, Jinbo Xu, Ming Li Rapid and Accurate Protein Side Chain Packing using Local Backbone Information RECOMB 2008 2008
4 Jing Xiao, Lusheng Wang, Xiaowen Liu and Tao Jiang Finding additive biclusters with random background The 19th Annual Symposium on Combinatorial Pattern Matching 2008
5 Pinyan Lu and Changyuan Yu  An Improveed Randomized Truthful Mechanism for Scheduling Unrelated Machines STACS 08 ¨Symposium on Theoretical Aspects of Computer Science 2008 2008 
6 Jie Yin, Yuexuan Wang, Cheng Wu Predictive Admission Control Algorithm for Advance Reservation in Equipment Grid 2008 International Conference on Services Computing (SCC2008) 2008
7 Bin Ma, Xiaoming Sun  More Efficient Algorithms for Closest String and Substring Problems RECOMB 2008 2008
8

 

 Chen Wang, Myung-Ah Park, James Willson, Yongxi Cheng, Andras Farago, Weili Wu On Approximate Optimal Dual Power Assignment for Biconnectivity and Edge-Biconnectivity Theoretical Computer Science 2008
9 Adam Tauman Kalai, Yishay Mansoury and Elad Verbinz On Agnostic Boosting and Parity Learning STOC 2008 2008
10 Jin-Yi Cai, Pinyan Lu Holographic Algorithms With Unsymmetric Signatures SODA 2008 2008
11 Yongxi Cheng, Xiaoming Sun, and Yiqun L. Yin Searching Monotone Multi-dimensional Arrays Discrete Mathematics 2008
12 Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew Chi-Chih Yao Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems CCC 2008 2008
13 Qingsong Ye, Huaxiong Wang and Christophe Tartary Privacy-Preserving Distributed Set Intersection Proceedings of the 2nd International Workshop on Advances in Information Security (WAIS 2008) 2008
14 Bin Ma and Hongyi Yao Seed Optimization Is No Easier than Optimal Golomb Ruler Design APBC2008, Sixth Asia-Pacific Bioinformatics Conference 2008
15 Yang Ye, Dapeng Lv, Yu Liu, Jianhua Feng Privacy Preservation for Multiple Sensitive Attributes SIGMOD 2008 (post) 2008
16 Yang Ye, Dapeng Lv, Yu Liu, Chi Wang, and Jianhua Feng BSGI: An Effective Algorithm towards Stronger l-diversity DEXA 2008 2008
17 Andrej Bogdanov, Elchanan Mossel and Salil Vadhan The complexity of distinguishing Markov Random Fields Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM 2008) 2008
18 Jin-Yi Cai, Pinyan Lu and Mingji Xia Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness FOCS 2008 2008
19 Deeparnab Chakrabarty, Gagan Goel, Vijay V. Vazirani, Lei Wang and Changyuan Yu

Effciency, Fairness and Competitiveness in Nash Bargaining Games

 WINE 2008 2008
20 Pinyan Lu and Changyuan Yu

Randomized Truthful Mechanisms for Scheduling Unrelated Machines

 WINE 2008 2008
21 Pinyan Lu, Changyuan Yu

Worst-Case Nash Equilibria in Restricted Routing

 WINE 2008 2008
22 Yingchao Zhao, Wei Chen and Shang-Hua Teng

The Isolation Game: A Game of Distances

 ISAAC 2008
23 Xiaoming Sun, Andrew Chi-Chih Yao and Christophe Tartary 

Graph Design for Secure Multiparty Computation over Non-Abelian Groups

 Asiacrypt 2008
24 Youming Qiao,Christophe Tartary

Counting Method For Multi-Party Computation over Non-Abelian Groups

 CANS2008 2008
25 Tiancheng Lou,Christophe Tarary

Analysis and Design of Multiple Threshold Changeable Secret Sharing Schemes

 CANS2008 2008
26 Christophe Tartary,Sujing Zhou,Dongdai Lin,Huaxiong Wang and Josef Pieprzyk

Analysis of Bilinear Pairing-based Accumulator for Identity Escrowing

 IET Information Security 2008
27 Jinyi Cai and Pinyan LU

Bases Collapse in Hologeaphic Algorithms

 COMPUTATIONAL COMPLEXITY 2008
28 Christophe Tartary, Huaxiong Wang and Josef Pieprzyk

A Coding Approach to the Multicast Stream Authentication Problem

 International Journal of Information Security 2008
29 Jing Xiao, Lusheng Wang, Xiaowen Liu and Tao Jiang

An Efficient Voting Algorithm for Finding Additive Biclusters With Random background

Journal of Computational Biology 2008
30 Yongxi Cheng, Ker-I Ko, and Weili Wu On the complexity of non-unique probe selection Theoretical Computer Science 2008

 



2007
  Authors Title Journal/Meeting Date
1 Xiaoming Sun and David Woodruff 　 The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences SODA 2007 2007
2 Xi Chen, Shang-Hua Teng and Paul Valiant The Approximation Complexity of Win-Lose Games SODA 2007 2007
3 Jing Xiao, Lan Liu, Lirong Xia and Tao Jiang Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree SODA 2007 2007
4 Zhang J, Jiang B, Li M, Tromp J, Zhang XG and Zhang MQ Computing exact p-values for DNA motifs (part I) Bioinformatics (Advance Access published) 2007
5 Jin-Yi Cai and Pinyan Lu On Symmetric Signatures in Holographic Algorithms STACS 2007 2007
6 Hongxu Cai, Zhong Shao, and Alexander Vaynberg Certified Self-Modifying Code In Proc. 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07), San Diego, CA, pages. 2007
7 Jin-Yi Cai and Pinyan Lu Holographic Algorithms: From Art to Science STOC 2007 . Also available at Electronic Colloquium on Computational Complexity Report TR06-145 (ECCC Report) 2007
8 Jin-Yi Cai and Pinyan Lu Bases Collapse in Holographic Algorithms CCC 2007. Also available at Electronic Colloquium on Computational Complexity Report TR07-003 (ECCC Report) 2007
9 Jin-Yi Cai, Vinay Choudhary and Pinyan Lu On the Theory of Matchgate Computations CCC 2007. Also available at Electronic Colloquium on Computational Complexity Report TR07-003 (ECCC Report) 2007
10 Yingchao Zhao and Shang-Hua Teng Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces TAMC 2007 2007
11 Jin-Yi Cai and Pinyan Lu Holographic Algorithms: The Power of Dimensionality Resolved ICALP 2007 2007
12 Jin-Yi Cai and Pinyan Lu On Block-wise Symmetric Signatures for Matchgates FCT 2007 2007
13 Yongxi Cheng, Xi Chen, and Yiqun L. Yin On Searching a Table Consistent with Division Poset Theoretical Computer Science, 370 (2007), 240-253 2007
14 Yongxi Cheng Lattice grids and Prisms are Antimagic Theoretical Computer Science, 374 (2007), 66-73 2007
15 Wei Chen, Jialin Zhang, Yu Chen, Xuezheng Liu Weakening Failure Detectors for k-Set Agreement via the Partition Approach DISC 2007, the 21st International Symposium on Distributed Computing 2007
16 Myung-Ah Park, Chen Wang, James Willson,  My Thai, Weili Wu, Andras Farago A dominating and absorbent set in a wireless ad-hoc network with different transmission ranges MobiHoc 2007 2007
17 Chen Wang, My Thai, Yingshu Li, Feng Wang, Weili Wu Minimum Coverage Breach and Maximum Network Lifetime in Wireless Sensor Networks Globecom 2007 2007
18 Lan Liu, Xi Chen, Jing Xiao and Tao Jiang Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem Theoretical Computer Science 2007
19 Jie Yin, Junwei Cao, Yuexuan Wang, Lianchen Liu, and Cheng Wu Scheduling remote access to scientific instruments in cyberinfrastructure for education and research CCGrid 2007 2007
20 Jie Yin, Yuexuan Wang, Cheng Wu An approach to build accessible grid service SNPD 2007 2007
21 Jie Yin, Yuexuan Wang, Cheng Wu A fuzzy scheduling method in equipment grid ICMCL 2007 2007
22 Yongxi Cheng Generating Combinations by Three Basic Operations Journal of Computer Science and Technology, 22 (6), 909-913, 2007 2007
23 Xi Chen and Shang-Hua Teng Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation FOCS 2007 2007
24 Yongxi Cheng and Ding-Zhu Du Efficient Constructions of Disjunct Matrices with Applications to DNA Library Screening Journal of Computational Biology, 14 (9), 1208-1216, 2007 2007
25 C. Tartary, H. Wang and J. Pieprzyk An Hybrid Approach for Efficient Multicast Stream Authentication over Unsecured Channels Proceedings of the 1st International Conference on Provable Security (ProvSec 2007) 2007
26 Christophe Tartary, Josef Pieprzyk and Huaxiong Wang. Verifiable Multi-Secret Sharing Schemes for Multiple Threshold Access Structures Proceedings of the 3rd SKLOIS Conference on Information Security and Cryptology (INSCRYPT 2007) 2007
27 Jing Zhang, Xi Chen, Ming Li Computing exact p-value for structured motif The 18th Annual Symposium on Combinatorial Pattern Matching 2007
28 Rui Wang, Francis C.M. Lau and Yingchao Zhao Hamiltonicity of regular graphs and blocks of consecutive ones in
symmetric matrices		 Discrete Applied Mathematrics 2007
29 Xiaoming Sun Block Sensitivity of Weakly Symmetric Functions Theoretical Computer Science 2007
30 Wei Chen, Jialin Zhang, Yu Chen Failure Detectors and Extended Paxos for k-Set Agreement PRDC2007 2007


2006
  Authors Title Journal/Meeting Date
1 Minming Li, Andrew C. Yao, and Frances F. Yao Discrete and continuous min-energy schedules for variable voltage processors Proceedings of US National Academy of Sciences, Vol.103(11)  2006
2 Xi Chen and Xiaotie Deng Settling the Complexity of 2-Player Nash-Equilibrium FOCS 2006 2006
3 Xiaoming Sun, Andrew C. Yao On the Quantum Query Complexity of Local Search in Two and Three Dimensions FOCS 2006  2006
4 Xi Chen, Xiaotie Deng and Shang-Hua Teng Computing Nash Equilibria: Approximation and Smoothed Complexity FOCS 2006  2006
5 David P. Woodruff Lower Bounds for Additive Spanners, Emulators, and More FOCS 2006  2006
6 Craig Gentry, Zulfikar Ramzan and David P. Woodruff Explicit Exclusive Set Systems with Applications to Broadcast Encryption FOCS 2006 2006
7 David P. Woodruff Better Approximations for the Minimum Common Integer Partition Problem APPROX-RANDOM 2006 2006
8 Piotr Indyk and David P. Woodruff Polylogarithmic Private Approximations and Efficient Matching TCC 2006 2006
9 Piotr Indyk and David P. Woodruff Fast Algorithms for the Free Riders Problem in Broadcast Encryption CRYPTO 2006 2006
10 Pinyan Lu, Shanghua Teng, Changyuan Yu Truthful Auctions with Optimal Profit WINE 2006 2006
11 Xi Chen, Xiaotie Deng and Shang-Hua Teng Sparse Games are Hard WINE 2006  2006
12 Xi Chen, Xiaotie Deng and Shang-Hua Teng Market Equilibria with Hybrid Linear-Leontief Utilities WINE 2006  2006
13 Xi Chen and Xiaotie Deng A Simplicial Approach for Discrete Fixed Point Theorems COCOON 2006 2006
14 Xi Chen, Xiaotie Deng and Becky Jie Liu On Incentive Compatible Competitive Selection Protocol COCOON 2006 2006
15 Xi Chen and Xiaotie Deng On the Complexity of 2D Discrete Fixed Point Problem ICALP 2006 2006
16 Xi Chen and Xiaotie Deng Lattice Embedding of Direction-Preserving Correspondence Over Integrally Convex Set AAIM 2006 2006
17 Jinyi Cai, Pinyan Lu On Symmetric Signatures in Holographic Algorithms Electronic Colloquium on Computational Complexity, No.135 2006
18 Jinyi Cai, Pinyan Lu Holographic Algorithms: From Art to Science Electronic Colloquium on Computational Complexity, No.145 2006
19 Yanhong A. Liu, Chen Wang, Michael Gorbovitski, Tom Rothamel, Yongxi Cheng, Yingchao Zhao, Jing Zhang Core role-based access control: efficient implementations by transformations PEPM' 06, 2006, 112-120 2006


2005
  Authors Title Journal/Meeting Date
1 Xi Chen and Xiaotie Deng On Algorithms for Discrete and Approximate Brouwer Fixed Points STOC 2005 2005
2 Xiaoming Sun, Runyao Duan, Mingsheng Ying The Existence of Quantum Entanglement Catalysts IEEE TRANSACTIONS ON INFORMATION THEORY 51(1) 2005
3 Lan Liu, Xi Chen, Jing Xiao and Tao Jiang Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem ISAAC 2005 2005
4 Hongxu CAI, Yingchao Zhao On Approximation Ratios of Minimum-Energy Multicast Routing in Wireless Networks Journal of Combinatorial Optimization No.9 2005
5 Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jinyi Cai Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs ISAAC 2005 2005


2004
  Authors Title Journal/Meeting Date
1 Andrew C. Yao Graph Entropy and Quantum Sorting Problems STOC 2004 2004
2 Xiaoming Sun, Andrew C.Yao, Shenyu Zhang Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? IEEE Conference on Computational Complexity (CCC 2004) 2004
3 Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao Fisher Equilibrium Price with a Class of Concave Utility Functions ESA 2004 2004
4 Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao Dynamic Price Sequence and Incentive Compatibility ICALP 2004 2004
5 Ning Chen, Xiaotie Deng, Xiaoming Sun On complexity of single-minded auction Journal of Computer and System Science, No.69 2004
6 Minming Li, Shawn L. Huang, Xiaoming Sun, Xiao Huang Performance evaluation for energy efficient topologic control in ad hoc wireless networks Theoretical Computer Science, No.326 2004




Copyright 2006-2007, Institute for Computer Science, Tsinghua University, All Rights Reserved.