On the Complexity of Trial and Error Shengyu Zhang Joint work with Xiaohui Bei and Ning Chen STOC'13,also at arXiv:1205.1183
Shengyu Zhang Joint work with Xiaohui Bei and Ning Chen STOC’13, also at arXiv:1205.1183
Motivating example:drug development Pandemic Consider an infectious disease outbreak due to an unknown virus. 。 Biochemists:find diagnosticreagents that have no serious side effects... ...as quickly as possible! PANDEMIC (Simplified)formulation Each side effect:certain combination of some ingredients Goal:find effective reagent/medicine without major side effect
Motivating example: drug development 2 • Consider an infectious disease outbreak due to an unknown virus. • Biochemists: find diagnostic reagents that have no serious side effects… … as quickly as possible! Pandemic • Each side effect: certain combination of some ingredients • Goal: find effective reagent/medicine without major side effect. (Simplified) formulation
Known vs.unknown If the virus(its DNA sequence,chemical composition,...) and its interactions to human body are known,then the reagent is much easier to find. Unfortunately,often the virus causing a pandemic is largely unidentified human body is too complicated a system to fully understand ●Learn it first?Efficiency！ 3
If the virus (its DNA sequence, chemical composition, …) and its interactions to human body are known, then the reagent is much easier to find. Unfortunately, often the virus causing a pandemic is largely unidentified. human body is too complicated a system to fully understand Learn it first? Efficiency! 3 Known vs. unknown
Standard method for drug development:Trial and error Candidate reagent allergic reaction, No side effect Side effect severe headache, MISSION ACCOMPLISHED 4
Candidate reagent No side effect Side effect 4 Standard method for drug development: Trial and error allergic reaction, severe headache, …
Phenomena Task:search for a solution (reagents)to satisfy a bunch of constraints(no side effect). Input(virus,human body):unknown. Allowed operations:solution testing. Approach:trial-and-error. Efficiency is crucial preferably better than learning the unknown input. ●Next:More examples. 5
Task: search for a solution (reagents) to satisfy a bunch of constraints (no side effect). Input (virus, human body): unknown. Allowed operations: solution testing. Approach: trial-and-error. Efficiency is crucial preferably better than learning the unknown input. Next: More examples. 5 Phenomena