<p>Since you mentioned signal processing, you should look at the area of <a href="http://en.wikipedia.org/wiki/Compressed_sensing" rel="noreferrer">"compressive sensing"</a>.  Here is an excellent non-technical description of the main ideas involved: <a href="http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/" rel="noreferrer">http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/</a></p>

CC BY-SA 2.5
2010-10-13T15:50:42.177Z
2010-10-13T15:50:42.177Z
arnab
<p>You might want to see if there are any problems in verifying hybrid systems (aka cyberphysical systems) that you want to tackle. The interaction of discrete control with continuous systems is pretty fascinating, and lets you add some logic and model theory to control theory, and it has many useful applications, too (ie, any time a computer interacts with the world!). </p>

<p><a href="http://symbolaris.com/index.html" rel="nofollow">Andre Platzer's homepage</a> has a pretty good summary of this area. </p>

CC BY-SA 2.5
2010-10-13T09:52:08.143Z
2010-10-13T09:52:08.143Z
Neel Krishnaswami
<p>Another possible connection to explore is the use of coinduction and coalgebraic techniques for reasoning about control theoretic systems. <a href="http://homepages.cwi.nl/~janr/papers/" rel="nofollow">Jan Rutten</a> did some work in this directions some years ago, namely:</p>

<ul>
<li>J.J.M.M. Rutten <em>Coalgebra, concurrency, and control.</em> In: R. Boel and G. Stremersch (eds.), Discrete Event Systems (analysis and control), Proceedings of WODES 2000 (5th Workshop on Discrete Event Systems), Kluwer, 2000, pp. 31--38.  (This link to the paper seems to be broken, though).</li>
</ul>

<p>The coalgebraic tecnology has advanced in the last 10 years, though I don't know whether the connection has been further explored. <strong>Edit</strong> <a href="http://www.math.cas.cz/~komenda/" rel="nofollow">Jan Komenda</a> (and <a href="http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/k/Komenda%3aJan.html" rel="nofollow">here</a>) seems to have been following up the connection. </p>

<p>Other possible approaches could involve using process algebra, I/O automata, interface automata, and hybrid variants of these things. The interface automata have a very strong <em>game theoretic</em> feeling which corresponds closely to somethings done in control theory, namely, the distinction between controllable and uncontrollable actions can be though of as actions being played by two different players. I'm not sure whether anything has been done in that area. The connection seems quite obvious. </p>

<p>A final connection that could be worth exploring is between control theory and epistemic logic. The connection can be seen via the games analogy. What does each party know? How can they use that to achieve a suitable outcome in the system being controlled?</p>

CC BY-SA 2.5
2010-10-13T13:07:48.847Z
2010-10-14T07:57:15.970Z
2010-10-14T07:57:15.970Z
Dave Clarke
<p>Robotics (or as it is all too often called these days, "cyberphysical systems") is a good source of problems that require both control theory and algorithms.  See Steve Lavalle's <a href="http://planning.cs.uiuc.edu/" rel="nofollow"><em>Planning Algorithms</em></a> for a good intro.</p>

CC BY-SA 2.5
2010-10-13T14:31:57.450Z
2010-10-13T14:31:57.450Z
Jeffε
<p>Social choice seems to be a nice area at the crossroads of many fields: control theory, complexity, etc. Moreover, it is always a surprise (I mean to me) to see that the problems of the guys from the dept of economics are almost the same as the ones we are trying to solve...
Believe me, it is worth having a coffee with them (and let them pay, they won't mind ;)).</p>

CC BY-SA 2.5
2010-10-13T23:34:07.720Z
2010-10-13T23:34:07.720Z
Sylvain Peyronnet
<p>A good area to explore could be the theory of optimal control (i.e., controlling a system while minimizing some given cost function), which was mainly developed by Richard Bellman, together with the dynamic programming paradigm, that is now ubiquitous in computer science.</p>

<p>A very useful application of optimal control is found, e.g., in Markov decision processes: a dynamical system is modeled by a Markov chain which can be altered by using some admissible policies. Costs are given for transitions and/or controls and one is usually interested in finding a policy that minimizes the total/average/discounted cost for a finite/infinite temporal horizon. This can be accomplished, e.g., by formulating a suitable Hamilton-Jacobi-Bellman equation for the system and then solving it by means of dynamic programming (many other methods exist depending on the systems).</p>

<p>Hence a natural application is in stochastic optimization settings in which the dynamical system can be modeled as Markovian. A standard reference for optimal control is:</p>

<ul>
<li>Dimitri P. Bertsekas, <em>Dynamic Programming and Optimal Control</em>, Athena Scientific.</li>
</ul>

CC BY-SA 2.5
2010-10-14T12:13:59.023Z
2010-10-14T12:13:59.023Z
cesco
<p>How about using optimization algorithms (such as Simulated Annealing or Genetic) to tune the parameters of your choice of control loop algorithm?</p>

CC BY-SA 2.5
2010-10-14T07:07:28.073Z
2010-10-14T07:07:28.073Z
David Reis
<p>There is some work on robust/private control that would benefit from a cryptographic perspective</p>

CC BY-SA 4.0
2021-08-16T21:20:12.030Z
2021-08-16T21:20:12.030Z
user6584
<p>I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.</p>

<p>I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.</p>

<p>The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.</p>

<p>It would be great if you could share which topic you think belongs to both worlds.</p>

<p>PS: This question might be totally out of the scope of this Q&amp;A site, so I totally agree if you feel like it's worth closing. Thanks!</p>

CC BY-SA 4.0
2021-08-16T16:04:44.470Z
y, thanks to the latest dependencied , space problem , where would i keep academic material i am practically tacking naturally throw-out but I will read more this before obvious whole interest now.
herberto silva
CC BY-SA 4.0
2021-08-16T23:04:37.017Z
Congestion control (in networks) is sort of in the intersection of control theory and TCS. (example of applying TCS in this context: https://doi.org/10.1109/SFCS.2002.1181953)
Neal Young
CC BY-SA 2.5
2010-10-13T09:36:39.033Z
So you are basically asking if there are any theoretical computer science approaches to control theory?
András Salamon
CC BY-SA 2.5
2010-10-13T09:39:21.587Z
Yes, it should be plenty of results from TCS that can be applied in control theory and I am interested in which are those.
hyperboreean
CC BY-SA 2.5
2010-10-13T10:31:26.417Z
Thanks Kaveh, I've edited the title to be more suggestive.
hyperboreean
<reference-request><soft-question>
Interdisciplinary topics between control theory and theoretical computer science
hyperboreean
# Interdisciplinary topics between control theory and theoretical computer science

(Asked by: username_0 on 2010-10-13)

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.

I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.

The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.

It would be great if you could share which topic you think belongs to both worlds.

PS: This question might be totally out of the scope of this Q&A site, so I totally agree if you feel like it's worth closing. Thanks!

**Tags:** reference-request, soft-question
> **Comments:**
> **username_3**: So you are basically asking if there are any theoretical computer science approaches to control theory?  
> **username_0**: Yes, it should be plenty of results from TCS that can be applied in control theory and I am interested in which are those.  
> **username_0**: Thanks Kaveh, I've edited the title to be more suggestive.  
> **username_1**: y, thanks to the latest dependencied , space problem , where would i keep academic material i am practically tacking naturally throw-out but I will read more this before obvious whole interest now.  
> **username_2**: Congestion control (in networks) is sort of in the intersection of control theory and TCS. (example of applying TCS in this context: https://doi.org/10.1109/SFCS.2002.1181953)  

---

## 8 answers

### Answer by username_4 on 2010-10-13. Score: 10

Since you mentioned signal processing, you should look at the area of ["compressive sensing"](http://en.wikipedia.org/wiki/Compressed_sensing). Here is an excellent non-technical description of the main ideas involved: <http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/>


---

### Answer by username_5 on 2010-10-13. Score: 7

You might want to see if there are any problems in verifying hybrid systems (aka cyberphysical systems) that you want to tackle. The interaction of discrete control with continuous systems is pretty fascinating, and lets you add some logic and model theory to control theory, and it has many useful applications, too (ie, any time a computer interacts with the world!).

[Andre Platzer's homepage](http://symbolaris.com/index.html) has a pretty good summary of this area.


---

### Answer by username_6 on 2010-10-13. Score: 6

Another possible connection to explore is the use of coinduction and coalgebraic techniques for reasoning about control theoretic systems. [Jan Rutten](http://homepages.cwi.nl/~janr/papers/) did some work in this directions some years ago, namely:

* J.J.M.M. Rutten *Coalgebra, concurrency, and control.* In: R. Boel and G. Stremersch (eds.), Discrete Event Systems (analysis and control), Proceedings of WODES 2000 (5th Workshop on Discrete Event Systems), Kluwer, 2000, pp. 31--38. (This link to the paper seems to be broken, though).

The coalgebraic tecnology has advanced in the last 10 years, though I don't know whether the connection has been further explored. **Edit** [Jan Komenda](http://www.math.cas.cz/~komenda/) (and [here](http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/k/Komenda%3aJan.html)) seems to have been following up the connection.

Other possible approaches could involve using process algebra, I/O automata, interface automata, and hybrid variants of these things. The interface automata have a very strong *game theoretic* feeling which corresponds closely to somethings done in control theory, namely, the distinction between controllable and uncontrollable actions can be though of as actions being played by two different players. I'm not sure whether anything has been done in that area. The connection seems quite obvious.

A final connection that could be worth exploring is between control theory and epistemic logic. The connection can be seen via the games analogy. What does each party know? How can they use that to achieve a suitable outcome in the system being controlled?


---

### Answer by username_7 on 2010-10-13. Score: 5

Robotics (or as it is all too often called these days, "cyberphysical systems") is a good source of problems that require both control theory and algorithms. See Steve Lavalle's [*Planning Algorithms*](http://planning.cs.uiuc.edu/) for a good intro.


---

### Answer by username_8 on 2010-10-13. Score: 3

Social choice seems to be a nice area at the crossroads of many fields: control theory, complexity, etc. Moreover, it is always a surprise (I mean to me) to see that the problems of the guys from the dept of economics are almost the same as the ones we are trying to solve...
Believe me, it is worth having a coffee with them (and let them pay, they won't mind ;)).


---

### Answer by username_9 on 2010-10-14. Score: 3

A good area to explore could be the theory of optimal control (i.e., controlling a system while minimizing some given cost function), which was mainly developed by Richard Bellman, together with the dynamic programming paradigm, that is now ubiquitous in computer science.

A very useful application of optimal control is found, e.g., in Markov decision processes: a dynamical system is modeled by a Markov chain which can be altered by using some admissible policies. Costs are given for transitions and/or controls and one is usually interested in finding a policy that minimizes the total/average/discounted cost for a finite/infinite temporal horizon. This can be accomplished, e.g., by formulating a suitable Hamilton-Jacobi-Bellman equation for the system and then solving it by means of dynamic programming (many other methods exist depending on the systems).

Hence a natural application is in stochastic optimization settings in which the dynamical system can be modeled as Markovian. A standard reference for optimal control is:

* Dimitri P. Bertsekas, *Dynamic Programming and Optimal Control*, Athena Scientific.


---

### Answer by username_10 on 2010-10-14. Score: 1

How about using optimization algorithms (such as Simulated Annealing or Genetic) to tune the parameters of your choice of control loop algorithm?


---

### Answer by username_11 on 2021-08-16. Score: 0

There is some work on robust/private control that would benefit from a cryptographic perspective


---

