Transcript Algorithms and Bioinformatics (a.k.a. Theory Group)

Theory Group
Faculty Members:
- Prof. Tak-Wah Lam
- Dr. Hing-Fung Ting
- Dr. Siu-Ming Yiu
- Dr. Giulio Chiribella
- Dr. Bruno Oliveira
- Dr. Hubert Chan
- Dr. Zhiyi Huang
Bioinformatics
Quantum Information
Programming Languages
Algorithms and Complexity
Zhiyi Huang
Background:
- B.E., Tsinghua University
- Ph.D., University of Pennsylvania
Research Interest:
- Theoretical Computer Science
- Algorithmic game theory, online algorithm,
privacy-preserving computation
Computer Science Meets Economics
The Internet created a new economy:
- Ad Auctions (Baidu, Google, Microsoft Bing)
- Auctions on Taobao and eBay
New Challenges
- Larger scale: (billions of users and transactions
per day) traditional auctions are not efficient.
[Cai and Huang SODA 2013] [Bei and Huang SODA 2011]
- More data: How to protect user privacy?
How to design auctions based on data?
[Huang, Mansour, and Roughgarden EC 2015]
[Hsu, Huang, Roth, Roughgarden, and Wu STOC 2014]
[Huang and Kannan FOCS 2012]
- Online decisions: E.g., how to adjust reserve
prices over time without knowing the future?
[Huang and Kim SODA15]
[Devanur, Huang, Korula, Mirrokni, and Yan EC 2013]
[Chakraborty, Huang, and Khanna FOCS 2009]
Network/Graph Algorithms
Faculty Member:
- Hubert Chan (Ph.D., Carnegie Mellon University)
Students:
- Zhichao Zhao (PhD)
- Ning Kang (PhD)
- Zhihao Tang (PhD)
- Shaofeng Jiang (PhD)
- Chenzi Zhang (PhD)
- Wenbin Tang (MPhil)
Recent Work on
Oblivious Matching
Motivated by applications like kidney exchange,
greedy algorithms for querying an unknown graph to
find a maximum size matching has been studied.
query 1
query 2
query 3
query 4
query 5
Is 1 & 5 an edge?
No
6 & 2?
Yes
1 & 4?
4 & 5?
1 & 3?
1
6
2
5
3
No
Yes
4
No
Matching: (6, 2) and (4, 5)
- Deterministic query order: performance ratio 0.5.
- Randomized query order: should be better?
How difficult is the problem?
First Attempt:
- 0.5000025
[Aronson, Dyer, Frieze and Suen 1995]
It took 17 years to get a better analysis:
- 0.5039
[Poloczek and Szegedy FOCS 2012]
Recent result:
- 0.523
[Chan, Chen, Wu, and Zhao SODA 2014]
Bioinformatics
Faculty Members:
- Prof. Tak-Wah Lam
- Dr. Hing-Fung Ting
- Dr. Siu-Ming Yiu
Approach:
- Algorithms => Software => Technologies
=> Scientific findings
What is Bioinformatics?
Bioinformatics is about the computational analysis of
biological or genetic data (DNA, RNA).
- Applications: biological discovery, cancer
diagnostics, gene-based drug discovery
- Objectives: better algorithms & software in terms
of speed, sensitivity, and accuracy
- Other concerns: big data, high performance
computing
Example
Cancer (or genetic disease) diagnostic in a hospital.
- Data volume: a high-throughput DNA sequencer
(e.g., HiSeq X Ten), in 24 hours, can serve 60
patients (WGS) and produce 6,000 Gb data (or
40G random DNA fragments of length 150).
- Analysis: map each fragment (150) to a
reference genome (3G) and detect mutations.
Publications, Software, Industrial
Partnership
Publications:
- Bioinformatics, Journal of Computational Biology,
RECOMB, ISMB, ECCB
Software:
- IDBA, Meta-IDBA, SOAP3-dp
Industrial partnership:
- HKU-BGI Bioinformatics Algorithm Research
Laboratory
Research Grants
ITF Grants: (2013-15, HK$ 5.6 Million)
- A Genomic and Pharmaceutical Knowledge-based System
for Clinical Diagnosis and Case Repository
GRF Grants (2011-13, over HK$ 2.5 Million)
- Next-Generation Sequencing Algorithms
- Ultrafast SNP-sensitive & Gap-sensitive alignment of short
reads to human genome via better indexing
- Structural Alignment and prediction for non-coding RNAs
with triple helix structure)
Quantum Information and
Foundations
Faculty Members:
- Dr. Giulio Chiribella
Winner of Hermann Weyl Prize 2010
Students:
- Yuxiang Yang (PhD)
- Daniel Ebler (PhD)
Taking up the challenge
David Deutsch (Oxford), 1985:
Quantum Turing Machine
Peter Shor (MIT), 1994:
quantum factoring algorithm
in polynomial time
Lov Grover (Bell Labs), 1996:
quantum search algorithm
with quadratic speed-up
Research Topics
Quantum Information Theory: discover new machines and
protocols that can process information more efficiently
- What is the best way to copy data at the quantum scale?
- What is the minimum energy cost of a computation?
- How fast can a microscopic machine learn from its
environment?
Quantum Foundations: rebuild the laws of physics from ideas
about information and computation.
- In a sense, this can be considered as the modern version of
Hilbert’s Sixth Problem: Mathematical Treatment of the
Axioms of Physics
Programming
Languages
Programming Languages
Programming languages research team:
Dr Bruno C. d. S. Oliveira
Students:
X. Bi
H. Zhang
PROGRAMMING LANGUAGES ARE FUNDAMENTAL TO
PROGRAMMER PRODUCTIVITY
PROGRAMMING LANGUAGE RESEARCH AIMS AT:
- Allowing faster development cycles
- Supporting large-scale programming
- Preventing more bugs
BY CREATING NEW PROGRAMMING
LANGUAGES/ABSTRACTIONS
RESEARCH TOPICS
- BETTER PROGRAMMING MODELS FOR MULTI-CORE COMPUTING,
GPU PROGRAMMING
- BETTER MODULARITY ABSTRACTIONS FOR LARGE-SCALE
SOFTWARE
- FUNCTIONAL PROGRAMMING (SCALA, HASKELL, OCAML,
SCHEME …)
Thank you!