Algorithms in Geometry and Protein 3D Structures:
- Zhiyu Zhao, Bin Fu, Francisco J. Alanis, and Christopher M.
Summa, Feedback Algorithm and Web-Server for Protein Structure Alignment, In the Proceedings of LSS Computational Systems Bioinformatics Conference,
CSB2008. The journal version is in the Journal of Computational Biology, 2008, 15(5), pp. 505-524. (pdf file).
-
Zaixin Lu, Zhiyu Zhao,Sergio Garcia, Krishnakumar Krishnaswamy, and Bin Fu,
Search Similar Protein Structures with Classfication, Sequence and
3-D Alignments. Journal of Bioinformatics and Computational Biology, October, 2009.
- Zhiyu Zhao and Bin Fu, A Flexible Algorithm for Pairwise Protein Structure Alignment,
In the Proceedings of the 2007 International Conference on Bioinformatics and Computational Biology (BIOCOMP'07), pp. 16-22. ( pdf file). Web Server and its mirror server.
- Zaixin Lu, Zhiyu Zhao and Bin Fu, Efficient Protein Alignment Algorithm for Protein Search,
BMC Bioinformatics 2010, 11(Suppl 1):S34 (18 January 2010). Also presented at the Eighth Asia Pacific Bioinformatics Conference
Bangalore, India, 18-21 January 2010.
- Bin Fu and Zhixiang Chen, Sub-linear Time Width-Bounded Geometric Separator and Their Application to Protein Side-Chain Packing Problem. In the Proceedings of the Second
International Conference on Algorithmic Apsects in Information and Management,
Hong Kong, June 20-22, 2006, Lecture Notes in Computer Science 3328, pp.149-160.
( pdf file). The journal version is in the Journal of Combinatorial Optimization, v. 15, pp. 387-407. ( pdf file).
- Bin Fu,
Theory and Application of Width Bounded Geometric Separator,
Electronic
Colloquium on Computational Complexity 2005, TR05-13.
(pdf file).
In the Proceedings of the 23rd International Symposium on
Theoretical Aspects of Computer Science (STACS'06), 2006, Lecture
Notes in Computer Science 3884, Springer, pp. 277-288.
The journal version is the Journal of Computer and System Sciences, Vol. 77, 2011, pp. 379-392.
- Bin Fu, Sorinel Oprisan, and Lizhe Xu, Multi-directional Width-Bounded Geometric Separator and Protein Folding,
16th Annual International Symposium on Algorithms and Computation (ISAAC'05),
2005, Lecture Notes in Computer Science 3827, Springer, pp. 995-1006. (pdf file).
The journal version is in the International J. of Computational Geometry and Applications, (Vol. 18, Issue 5), pp. 389 - 413, October 2008.
(pdf file).
- Bin Fu and Wei Wang,
A 2^{O(n^{1-1/d}log n)} Time Algorithm for d-dimensional Protein Folding in
the HP-model,
Proceedings of 31st International Colloquium on Automata,
Languages and Programming (ICALP'2004), July 12-26, 2004, Turku, Finland,
Lecture Notes in Computer Science 3142, Springer 2004, pp.630-644. (pdf file).
The journal version is published in SIAM Journal on Computing (Vol.37, No.4), pp. 1014-1029, 2007.
- Mahdi Abdelguerfi, Zhixiang Chen, and Bin Fu,
On the Space Complexity of Approximation Streaming Algorithms for
the k-center Problem. In the Proceedings of
the 2007 International Frontiters of Algorithmics WorkShop(FAW 2007), Lecture Notes in Computer Science 4613, Springer, pp. 160-171.
- Bin Fu, Zhixiang Chen, and Mahdi Abdelguerfi,
An Almost Linear Time 2.8334-Approximation Algorithm for the Disc
Covering Problem. In the Proceedings of
the Third International Conference on Algorithmic
Aspects in Information and Management (AAIM 2007).
Lecture Notes in Computer Science, 4508
Springer, pp. 317-326. (pdf file ).
-
Zhixiang Chen, Bin Fu, Yong Tang, and Binhai Zhu,
A PTAS for a DISC Covering Problem Using Width-Bounded Separators,
In the Proceedings of the 11th International Computing and Combinatorics Conference, August 16-19, 2005, Kunming, Yunna, China, Lecture Notes in
Computer Science 3595, Springer, pp. 490-503.
The journal version is published in Journal of Combinatorial Optimization, March 2006, pp. 203-217. (pdf file).
-
Zaixin Lu, Zhiyu Zhao, Sergio Garcia, and Bin Fu,
New Algorithm and Web Server for Finding Proteins with Similar 3D Structures,
In the Proceedings of the International Conference on Bioinformatics and Computational Biology (BIOCOMP'08), pp. 674-680, 2008.
-
Bin Fu and Lusheng Wang, Constant Time Approximation Scheme for Largest Well Predicted Subset, In the Proceedings
of the 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Lecture Notes in Computer
Science 6196, pp. 429-438. The journal version has been accepted by the Journal of Combinatorical optimization.
-
Liang Ding, Bin Fu and Yunhui Fu, Improved Sublinear Time Algorithm for Width-Bounded Separators
In Proceedings of the Fourth International Frontiers of Algorithmics Workshop (FAW 2010), Lecture Notes in Computer Science 6213, 101-112.
-
Liang Ding, Bin Fu, Yunhui Fu and Yubing Wan, Application of Width-Bounded Separators to Protein Side Chain Packing Problem, To appear in the book: Sequence and Genome Analysis: Methods and Applications.
( Link ).
Algorithms in Genome Sequences:
-
Liang Ding, Bin Fu, and Binhai Zhu,
Minimum Interval Cover and Its Application to Genome Sequencing, Accepted by The 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11).
-
Bin Fu, Haitao Jiang, Boting Yang, and Binhai Zhu,
Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem, Accepted by The 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11).
-
Bin Fu and Louxin Zhang, A Polynomial Algebra Method for Computing Exemplar Breakpoint Distance, Accepted by The 7th International Symposium on Bioinformatics Research and Applications (ISBRA 2011).
-
Bin Fu and Yunhui Fu,
Sublinear Time Motif Discovery from Multiple Sequences, arXiv:1007.2618, July 2010. ( link )
-
Zhi-Zhong Chen, Bin Fu, Haitao Jiang, Yang Liu, Lusheng Wang, and Binhai Zhu,
A Linear Kernel for Co-Path/Cycle Packing, In the Proceedings of the Sixth International Conference on Algorithmic Aspects in Information and Management(AAIM'10), 2010,
Lecture Notes in Computer Science, to appear.
-
John Abraham, Zhixiang Chen, Richard Fowler, Bin Fu,and Binhai Zhu,
On the Approximability of Some Haplotyping Problems, In the Proceedings of the 5th International Conference on
Algorithmic Aspects in Information and Management (AAIM'09), Lecture Notes in Computer Science 5564, pp.3-14.
-
Zhixiang Chen, Bin Fu, Minghui Jiang, Binhai Zhu:
On Recovering Syntenic Blocks from Comparative Maps. In the Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08), Lecture Notes
in Computer Science 5165, pp. 319-327
-
Bin Fu, Ming-Yang Kao, and Lusheng Wang,
Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability,
In the Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC'09), 2009,
Lecture Notes in Computer Science 5532, pp.231-240. The journal version has been accepted by the ACM transaction on algorithm.
-
Bin Fu, Ming-Yang Kao, and Lusheng Wang,
Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences,
In the Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation (TAMC'08), 2008,
Lecture Notes in Computer Science 4978, pp. 234-245. The journal version is
in the SIAM Journal on Discrete Mathematics (Vol.23, No.4), 18 November 2009, pp. 1715-1737.
- Zhixiang Chen, Bin Fu, Robert Schweller, Boting Yang, Zhiyu Zhao and Binhai
Zhu,
Linear Time Probabilistic Algorithms for the Singular Haplotype
Reconstruction Problem from SNP Fragments. In The Proceedings of The Sixth Asia Pacific Bioinformatics Conference,
Kyoto, Japan, 14-17 January 2008, pp. 333-342. The journal version is in the Journal of Computational Biology, 2008, 15(5), pp. 535-546..
- Zhixiang Chen, Bin Fu, Jinhui Xu, Boting Yang, Zhiyu Zhao and Binhai
Zhu, Non-breaking Similarity of Genomes with Gene Repetitions.
In the Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, 2007. Lecture Notes in Computer Science 4580, Springer, 119-130. (pdf file).
- Zhixiang Chen, Richard Fowler, Bin Fu and Binhai Zhu, Lower Bounds on the Approximation of the Examplar Conserved Interval Distance Problem of Genomes.
In the Proceedings of the 12th Annual International Computing and Combinatorics
Conference (COCOON'06), Taipai, Taiwan, August 15-18, 2006,
Lecture Notes in Computer Science, 4112, pp 245-254.
( pdf file). The journal version is in the Journal of Combinatorial Optimization, v. 15, pp. 201-221.
- Zhixiang Chen, Bin Fu and Binhai Zhu, Approximations for the Exemplar Breakpoint Distance Problem. In the Proceedings of the Second International Conference on
Algorithmic Aspects in Information and Management, Hong Kong,
June 20-22, 2006, Lecture Notes in Computer Science 3328, pp. 291-302.
( pdf file).
Algorithms in Scheduling:
-
Bin Fu, Yumei Huo, and Hairong Zhao,
Exponential Inapproximability and FPTAS for Scheduling with Availability Constraints,
Theoretical Computer Science, 410:2663-2674, 2009.
-
Bin Fu, Yumei Huo, and Hairong Zhao,
Makespan minimization with machine availability constraints,
In the Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), 2009,
Lecture Notes in Computer Science, Lecture Notes in Computer Science 5573, pp.430-437.
The journal version is in Discrete Mathematics, Algorithms and Applications, , 1(2): 141-151, 2009.
-
Bin Fu, Yumei Huo, and Hairong Zhao,
Coordinated Scheduling of Production and Delivery with Production Window and Delivery Capacity Constraints,
In the Proceedings of the Sixth International Conference on Algorithmic Aspects in Information and Management(AAIM'10), 2010,
Lecture Notes in Computer Science 6124, pp. 141-149.
-
Bin Fu, Yumei Huo, and Hairong Zhao,
Approximation Schemes for Scheduling with Availability Constraints,
In the Proceedings of the Fourth International Frontiers of Algorithmics Workshop (FAW 2010), 2010,
Lecture Notes in Computer Science 6213, pp. 77-88. The journal version has been accepted by Applied Discrete Mathematics.
Algorithms in Other Topics:
-
Bin Fu,
Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage, arXiv: 1604.01421. ( link ).
- Zhixiang Chen and Bin Fu,
On the Complexity of Rocchio's Similarity-Based Relevance Feedback Algorithm,
16th Annual
International Symposium on Algorithms and Computation, December
19-21, 2005, Sanya, Hainan, China. Lecture Notes in Computer Science
3827, Springer, pp. 216-225.
(pdf file).
The journal version is published in the Journal of the American Society for Information Science and Technology, 58(10), 2007, pp. 1392-1400..
-
Zhixiang Chen and Bin Fu,
A Quadratic Lower Bound for Rocchio's Similarity-Based Relevance Feedback Algorithm,
In the Proceedings of the 11th International Computing and Combinatorics Conference, August 16-19, 2005, Kunming, Yunna, China, Lecture Notes
in
Computer Science 3595, Springer, pp. 955-964. (pdf file).
The journal version is the Journal of Combinatorial Optimization, 16(4), 2008.
- Bin Fu and Richard Beigel,
Diagnosis in the Presence of Intermittent Faults,
In the Proceedings of the 15th Annual Sympo sium on Algorithms and Computation (ISAAC'2004), December 20-22, 2004, Hong Kong, Lecture Notes in Computer Science 3341, Springer, pp.427-441. (pdf file).
-
Liang Ding, Bin Fu, Yunhui Fu, Zaixin Lu, and Zhiyu Zhao, O((\log n)^2) Time Online Approximation Schemes for Bin Packing and Subset Sum Problems
In Proceedings of the Fourth International Frontiers of Algorithmics Workshop (FAW 2010), Lecture Notes in Computer Science 6213, pp. 250-261.
-
Artem Chebotko and Bin Fu
Title: XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme, arXiv:1007.2671
( link ). In the Proceedings of the 4th International Conference on Combinatorial Optimization and Applications (COCOA 2010),
Lecture Notes in Computer Science 6509, pp. 97-106.
Algorithms in Algebra:
-
Li Chen and Bin Fu,
Linear and Sublinear Time Algorithms for the Basis of Abelian Groups,
Electronic
Colloquium on Computational Complexity, TR07-052, 2007.
(pdf file ). In the Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009). Lecture Notes in Computer Science 5878, pp. 493-502. The journal version will appear in Theoretical Computer Science.
-
Bin Fu and Zhixiang Chen, A Sublinear Time Randomized Algorithm for Coset Enumeration in the Black Box Model,
In the Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON'08), Lecture Notes in Computer Science 5092, pp. 82-91.
-
Bin Fu,
Testing Group Commutativity in Constant Time, Journal of Scientific and Practical Computing
Vol.3, No.1 (2009) 3-9. ( pdf file ).
-
Zhixiang Chen, Bin Fu, Yang Liu, and Robert Schweller, Algorithms for Testing Monomials in Multivariate Polynomials,
Electronic Colloquium on Computational Complexity (ECCC-TR10-122) ( link )
Computational Complexity Theory:
-
Bin Fu, Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP, Electronic Colloquium on Computational Complexity (ECCC-TR10-196) ( link ).
-
Bin Fu, NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets, Electronic Colloquium on Computational Complexity (ECCC-TR10-196) ( link ).
-
Zhixiang Chen and Bin Fu, Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials, Electronic Colloquium on Computational Complexity (ECCC-TR10-124) ( link ).
In the Proceedings of 4th International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science 6508, pp. 309-323.
-
Zhixiang Chen and Bin Fu, The Complexity of Testing Monomials in Multivariate Polynomials, Electronic Colloquium on Computational Complexity (ECCC-TR10-114) ( link .)
-
Richard Beigel, Bin Fu,
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing, Electronic Colloquium on Computational Complexity (ECCC-TR11-028)( link).)
-
Bin Fu, Angsheng Li, and Liyu Zhang,
Separating NE from Some Nonuniform Nondeterministic Complexity Classes, In the Proceedings of
the 15th International Computing and Combinatorics Conference (COCOON'2009), Lecture Notes
in Computer Science, 5609 pp. 486-495. The journal version has been accepted by the Journal of Combinatorial Optimization.
- Bin Fu and Zhiyu Zhao,
Separating Sublinear Time Computations by Approximate Diameter,
In the Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08), Lecture Notes
in Computer Science 5165, pp. 79-88. The journal version is in the Journal of Combinatorial Optimization,Volume 18, Number 4, November, 2009 pp. 393-416 .
- Richard Beigel and Bin Fu,
Circuits Over PP and PL,
Journal of Computer and Systems Sciences, 60(2000), pp. 422-441. (pdf file).
- Bin Fu,
With Quasi-linear Queries EXP is Not Polynomial-time
Turning Reducible to Sparse Sets.
SIAM Journal on Computing,
October, 1995, pp.1082-1090. (pdf file).
- Bin Fu and Hong-zhou Li,
Closeness of NP-hard Sets to Other Complexity Classes.
SIAM Journal on Computing, vol.23, No.2, April, 1994,
pp.255-260.
- Shouwen Tang, Bin Fu, Tian Liu,
Exponential Time and Sub-exponential Time Sets.
Theoretical Computer Science, 115(1993), pp.371-381.
- Bin Fu and Hong-zhou Li,
On Symmetric Difference of NP-hard Sets with Weakly-P-Selective
Sets. Theoretical Computer Science, 120(1993), pp.279-291.
- Bin Fu, Hong-zhou Li and Yong Zhong,
An Application of Translational Method. Mathematical Systems
Theory, 27(1994), pp.183-186.
(pdf file).
- Bin Fu,
On Lower Bounds of Closeness between Complexity Classes.
Mathematical Systems Theory, 26(1993), pp.187-202
- Bin Fu,
Separating PH from PP by Relativization. Acta Mathematica
Sinica, Vol.8, No.3, 1992, pp.329-336.
- Bin Fu, On P-Selective Sets and EXP Hard Sets,1997,
(pdf file).
This is an unpublished manuscript that was written in 1997
when I was visiting University of Maryland as a graduate student from Yale.
I just post it here since it was cited by some complexity scientists.
Software Security:
-
Bin Fu, Sai Krishna Aravalli, and John Abraham, Software Protection by Hardware and Obfuscation,
In Proceedings of the 2007 International Conference on Security and Management
(SAM'07), pp. 367-373. (pdf file).
- Bin Fu, Golden G. Richard III, Yixin Chen, Adbo Husseiny,
Some New Approaches for Preventing Software Tampering, In the Proceedings of the
44th ACM South East Conference (ACMSE'06), pp. 655-660. (pdf file).
Logic of Program:
- Bin Fu and Qiong-Zhang Li,
Expressibility of First Order Dynamic Logic. Journal of
Computer Science and Technology, Vol.7,No.3, 1992, pp.268-273. (pdf file ).
Molecular Computing:
- Bin Fu, Matthew J. Patitzy, Robert T. Schwellerz, and Robert Sheline,
Self-Assembly with Geometric Tiles, ICALP 2012, arXiv: 1104.2809v1. ( link ).
- Bin Fu and Richard Beigel,
Length Bounded Molecular Computing,
Bio Systems, 52 (1999), pp. 155-163
- Bin Fu, Richard Beigel, and Fang Xiao Zhou,
An O(2^n) Volume Molecular Algorithm for Hamiltonian Path,
Bio Systems, 52 (1999), pp. 217-226.
- Richard Beigel and Bin Fu,
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion,
Algorithmica, 25(1999), pp. 222-238. (pdf file).
- Bin Fu and Richard Beigel,
A Comparison of Resource-Bounded Molecular Computation Models.
Algorithmica, 24(1999), pp. 87-95.
- Richard Beigel and Bin Fu,
Solving Intractable Problems with DNA Computing, Thirteen Annual IEEE
Conference on Computational Complexity, June 15-18, 1998, 154-186.
- Bin Fu and Richard Beigel, Molecular Approximation Algorithm for NP
Optimization Problems, In Proceedings of Third Annual DIMACS Workshop on
DNA Computation(June 23-25, 1997, Philadephia), pp. 93-101.
Patents in Pattern Recognition:
- Bin Fu and Shang-Hung Lin,
Method and Apparatus for Calibrating a Computer Generated projected Image.
Patent Number 6,292,171. Approved on September 18,2001.
- Bin Fu and Anoop Bhattacharjya,
Image Processing Apparatus and Methods for Pattern Recognition.
Pattern Number 6,370,271. Approved on April 9, 2002.