<p>Just like quantum-computing, I suppose DNA-computing throws in a significantly different physical model of computing (ability to self-replicate). In principle that should stimulate significant cross research between theory and practice.</p>

<p>Another potential area is Goemetric Complexity Theory. At this point, of course it is probably the most abstruse area, and no one knows how the final shape will look like. But as Ketan Mulmuley had pointed out in one of his talks (I'll update the reference if I can find it) - that any success of GCT (or any P/NP separation work for that matter) will actually result in establishing the significant largeness of the class P - i.e., to successfully show complexity class separation and avoid Razborov-Rudich-type (or Aaronson-Wigderson-type ) barriers at the same time, one needs algorithms to solve problems for which at present only doubly or triply exponential solutions are known at best. If polynomial time algorithms are discovered, that could be a potential game-changer in many applied areas as well. </p>

CC BY-SA 3.0
2012-10-10T22:21:45.230Z
2012-10-10T23:02:56.097Z
2012-10-10T23:02:56.097Z
Arnab
<p>There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc.
But the thing with basic research is that it's hard to know in advance what's going to be influential, when and how.</p>

<p>One potential candidate could be quantum computing, which has strong ties to both physics and electronics, and could make a huge difference (allowing efficient simulations of quantum systems, breaking RSA, and more). However, it's hard to know when quantum computers will be built (if at all).</p>

CC BY-SA 3.0
2012-10-10T22:36:22.330Z
One thing that always fascinated me, is the fact that just like mathematics has huge implications in understanding the laws of nature ( for physicists to judge what nature may or may not allow), someday some of the TCS results may have similar implications. The P/NP question, the parallel repition theorem, etc., may have already made such implications.  But then, TCS, albeit studied in different departments in most universities, is probably just another branch of mathematics anyway.
Arnab
CC BY-SA 3.0
2012-10-09T15:36:56.813Z
2012-10-09T15:36:56.813Z
Dana Moshkovitz
<p>Another field that started out in TCS is formal verification. Two very theoretical and important results in the field are: Pnueli's paper on linear temporal logic (LTL) from 77 and Vardi and Wolper LTL to Buchi automata construction from the 80s. In the 90s, McMillan suggested to use BDDs in order to work with huge systems, and from that point the industry started using formal verification regularly. Now it's being used mainly in hardware, and there is much research on developing tools for software as well.</p>

CC BY-SA 3.0
2012-10-11T14:12:01.510Z
2012-10-11T14:12:01.510Z
Guy
<p>Fields such as bioinformatics and computational biology could fundamentally change the way we live since it may lead to revolutions in drugs manufacturing, disease prevention and treatment, and possibly synthetic biology. Currently, there is no formal language in TCS that explains how DNA code controls the functions of biological systems. There is no theory in TCS that determines the functions of some DNA segment. Research progress in those fields would have huge impact on medicine, biology and therefore society.</p>

CC BY-SA 3.0
2012-10-09T17:17:26.663Z
closely related, [protein folding problem,](http://en.wikipedia.org/wiki/Protein_folding_problem) mainly a physics simulation problem but with ties to TCS
vzn
CC BY-SA 3.0
2012-10-09T16:51:05.853Z
2012-10-09T17:51:10.810Z
2012-10-09T17:51:10.810Z
Mohammad Al-Turkistany
<p>While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.</p>

<p>As we know, P versus NP is often talked about with its relation to public crypto. systems. Moreover, streaming algorithms often directly lead to industrial benefits. </p>

<p>Is there any possible research direction that would satisfy the following conditions? </p>

<p>(1)Solving problems in this area of TCS would lead to a fundamental change in our society.</p>

<p>(2)It would be required to understand other academic subjects (such as physics or electronics) to solve problems related to this TCS field. </p>

<p>I am afraid that this question is not appropriate for this stack exchange, but please forgive me if it is.  </p>

CC BY-SA 3.0
2012-10-09T17:16:19.457Z
(2) is not clear. also keep in mind many algorithms have already had huge impact. AI & related areas (eg datamining) are big potential areas but its not always considered part of TCS(.se) ie maybe more applied
vzn
<soft-question>
TCS Research Frontier with Huge Practical and Industrial Impact on our Society
Elely
# TCS Research Frontier with Huge Practical and Industrial Impact on our Society

(Asked by: username_0 on 2012-10-09)

While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.

As we know, P versus NP is often talked about with its relation to public crypto. systems. Moreover, streaming algorithms often directly lead to industrial benefits.

Is there any possible research direction that would satisfy the following conditions?

(1)Solving problems in this area of TCS would lead to a fundamental change in our society.

(2)It would be required to understand other academic subjects (such as physics or electronics) to solve problems related to this TCS field.

I am afraid that this question is not appropriate for this stack exchange, but please forgive me if it is.

**Tags:** soft-question

> **Comments:**
> **username_1**: (2) is not clear. also keep in mind many algorithms have already had huge impact. AI & related areas (eg datamining) are big potential areas but its not always considered part of TCS(.se) ie maybe more applied  

---

## 4 answers

### Answer by username_2 on 2012-10-10. Score: 2 | Accepted answer

Just like quantum-computing, I suppose DNA-computing throws in a significantly different physical model of computing (ability to self-replicate). In principle that should stimulate significant cross research between theory and practice.

Another potential area is Goemetric Complexity Theory. At this point, of course it is probably the most abstruse area, and no one knows how the final shape will look like. But as Ketan Mulmuley had pointed out in one of his talks (I'll update the reference if I can find it) - that any success of GCT (or any P/NP separation work for that matter) will actually result in establishing the significant largeness of the class P - i.e., to successfully show complexity class separation and avoid Razborov-Rudich-type (or Aaronson-Wigderson-type ) barriers at the same time, one needs algorithms to solve problems for which at present only doubly or triply exponential solutions are known at best. If polynomial time algorithms are discovered, that could be a potential game-changer in many applied areas as well.


---

### Answer by username_3 on 2012-10-09. Score: 13

There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc.
But the thing with basic research is that it's hard to know in advance what's going to be influential, when and how.

One potential candidate could be quantum computing, which has strong ties to both physics and electronics, and could make a huge difference (allowing efficient simulations of quantum systems, breaking RSA, and more). However, it's hard to know when quantum computers will be built (if at all).

> **Comments:**
> **username_2**: One thing that always fascinated me, is the fact that just like mathematics has huge implications in understanding the laws of nature ( for physicists to judge what nature may or may not allow), someday some of the TCS results may have similar implications. The P/NP question, the parallel repition theorem, etc., may have already made such implications.  But then, TCS, albeit studied in different departments in most universities, is probably just another branch of mathematics anyway.  

---

### Answer by username_5 on 2012-10-09. Score: 5

Fields such as bioinformatics and computational biology could fundamentally change the way we live since it may lead to revolutions in drugs manufacturing, disease prevention and treatment, and possibly synthetic biology. Currently, there is no formal language in TCS that explains how DNA code controls the functions of biological systems. There is no theory in TCS that determines the functions of some DNA segment. Research progress in those fields would have huge impact on medicine, biology and therefore society.

> **Comments:**
> **username_1**: closely related, [protein folding problem,](http://en.wikipedia.org/wiki/Protein_folding_problem) mainly a physics simulation problem but with ties to TCS  

---

### Answer by username_4 on 2012-10-11. Score: 4

Another field that started out in TCS is formal verification. Two very theoretical and important results in the field are: Pnueli's paper on linear temporal logic (LTL) from 77 and Vardi and Wolper LTL to Buchi automata construction from the 80s. In the 90s, McMillan suggested to use BDDs in order to work with huge systems, and from that point the industry started using formal verification regularly. Now it's being used mainly in hardware, and there is much research on developing tools for software as well.


---

