# Bruno Frederik Bauwens

- Assistant Professor:Faculty of Computer Science / Big Data and Information Retrieval School
- Research Fellow:Faculty of Computer Science / Big Data and Information Retrieval School / Laboratory of Theoretical Computer Science

- Bruno Frederik Bauwens has been at HSE University since 2015.

### Education and Degrees

- 2010
PhD

Ghent University - 2005
Master's in Engineering

Ghent University - 2003
Bachelor's in Mathematics

Ghent University

### Student Term / Thesis Papers

- Bachelor
M. Urmanov, Universal Codes in the Shared-randomness Model for Channels with General Distortion Capabilities. Faculty of Computer Science, 2021

D. Kazantsev, Determining Triangle Ramsey Numbers. Faculty of Computer Science, 2021

D. Troshin, Implementation of a Fast Compression Algorithm Based on Hash-Functions. Faculty of Computer Science, 2021

A. Cherezova, Determining Triangle Ramsey Numbers. Faculty of Computer Science, 2021

I. Blinnikov, Non-Computability of Algorithmic Information Distance. Faculty of Computer Science, 2020

A. Uzikov, Determining Triangle Ramsey Numbers. Faculty of Computer Science, 2020

M. Gilmutdinov, Causal Relationships, New Approaches Inspired by Information Theory. Faculty of Computer Science, 2018

- Master
Y. Rebenko, Geometric Algorithms for Error-Correcting Quantum Codes. Faculty of Computer Science, 2021

### Courses (2020/2021)

Theoretical computer science 2018, for 1st-year PhD

----------------------------------------------------------------------Classes: Room 301, Monday 18h10-21h00.

(PDF, 141 Кб) Lect 1, 15/1: Discrete finite automata: basic properties, the equivalence of deterministic and non-deterministic machines.

(PDF, 278 Кб) Lect 2, 22/1: Equivalence regular expressions and regular languages. Turing machines and other models of computation.

(PDF, 303 Кб) (Update 28/02)Lect 3, 29/1: We continue the notes from the previous lecture.

Lect 4, 5/2: The halting problem, decidable and recognizable sets.

(PDF, 486 Кб) **(Updated 22/05)**Lect 5, 12/2: Some undecidable problems. See the notes from the previous lecture.

Lect 6, 19/2: Decidability of additive arithmetic. Godel's and Rosser's incompleteness theorems.

(PDF, 400 Кб) **(Updated 22/05)**Lect 7, 26/2: The class P and NP. NP-complete problems. We follow chapter 7 of Sipser's book.

(PDF, 175 Кб) (updated 27/02)(PDF, 134 Кб) **Intermediate exam, 3th of March, 12h00-15h00.**(updated 27/02)

Materials: lectures 1-7.

(PDF, 115 Кб) Lect 8, 3/3 from 16h00-18h30: Discussion exam.

Lect 9, 5/3: NP-completeness of 3SAT, 1-3-SAT, NAE-3SAT, Clique, Subsetsum, 0-1 integer programming, and many other examples.

**Deadline project, Sunday 11/3, 23h59.****12/3:****no lecture.**Lect 10, 19/3: NP-Completeness of HAMPATH, a few more exercises about NP and coNP. Classes PSPACE, NPSPACE, EXPSPACE, Savitch theorem and PSPACE complete problems. (Chapter 8 in Sipser's book).

(PDF, 283 Кб) Lect 11, 2/4: More on PSPACE.

(PDF, 141 Кб) (PDF, 176 Кб) Lect 12, 9/4: Pspace completeness of generalized geography. Time and Space hierarchy theorems. Oracle computations. (Sections 8.3, 9.1 and 9.2).

(PDF, 92 Кб) (PDF, 139 Кб) **Saturday 14/4, final exam, 12h00-15h30. Room 400.**

Materials: Exercises from lectures 7-12. Sipser's book Chapter 7, Sections 8.1-8.3, and Chapter 9 except for Theorem 9.20(1), and exercises from the seminar sheets.Project presentations: Saturday 24/3, 31/3, 7/4 and 21/4. (There will be a doodle when you submit the paper.)

**Saturday 2/6, intermediate and final exam, 12h00-19h00, room 412.****Saturday 16/6, intermediate and final exam, 12h00-15h00, room 412.****August: Exam for those who did not pass.**(PDF, 372 Кб) - Statistical Learning Theory (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Eng
- Statistical Learning Theory (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
- Statistical Learning Theory (Master’s programme; Faculty of Computer Science; 2 year, 1, 2 module)Eng
- Theory of Computation (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
- Theory of Computation (Master’s programme; Faculty of Computer Science; 1 year, 1, 2 module)Eng
- Past Courses

### Courses (2019/2020)

- Theory of Computation (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
- Theory of Computation (Master’s programme; Faculty of Computer Science; 1 year, 1, 2 module)Eng

### 2020^{3}

- Chapter Bauwens B. F. Information Distance Revisited, in:
*37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)*Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. doi P. 46:1-46:14. doi - Chapter Bauwens B. F., Blinnikov I. The normalized algorithmic information distance can not be approximated, in:
*Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings*Vol. 12159. Springer, 2020. doi P. 130-141. doi - Article Bauwens B. F. Uniform van Lambalgen's theorem fails for computable randomness //
*Information and Computation*. 2020. Vol. 271. No. 104486. P. 1-6. doi

### 2018^{2}

- Article Kertesz-Farkas A., Bauwens B. F., Filatov G. LZW-Kernel: fast kernel utilizing variable length code blocks from LZW compressors for protein sequence classification //
*Bioinformatics*. 2018. Vol. 34. No. 19. P. 3281-3288. doi - Article Vereshchagin N., Bauwens B. F., Makhlin A., Zimand M. Short lists with short programs in short time //
*Computational Complexity*. 2018. Vol. 27. No. 1. P. 31-61. doi

### 2017^{3}

- Article Bauwens B. F. Conditional Measure and the Violation of Van Lambalgen’s Theorem for Martin-Löf Randomness //
*Theory of Computing Systems*. 2017. Vol. 60. No. 2. P. 314-323. doi - Article Bauwens B. F., Shen A., Takahashi H. Conditional Probabilities and van Lambalgen’s Theorem Revisited //
*Theory of Computing Systems*. 2017. Vol. 61. No. 4. P. 1315-1336. doi - Article Antunes L., Bauwens B. F., Souto A., Teixeira A. Sophistication vs Logical Depth //
*Theory of Computing Systems*. 2017. Vol. 60. No. 2. P. 280-298. doi

### 2015^{2}

- Article Bauwens B. F. Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs //
*Archive for Mathematical Logic*. 2015. Vol. 54. No. 5. P. 615-629. doi - Article Bauwens B. F. Relating and contrasting plain and prefix Kolmogorov complexity //
*Theory of Computing Systems*. 2015. Vol. 58. No. 3. P. 482-501. doi

### 2013^{2}

- Article Bauwens B. F., Shen A. An additivity theorem for plain Kolmogorov complexity //
*Theory of Computing Systems*. 2013. Vol. 52. No. 2. P. 297-302. - Article Bauwens B. F., Shen A. Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity //
*Journal of Symbolic Logic*. 2013. Vol. 79. No. 2. P. 620-632.

### 2011^{1}

*Theory of Computing Systems*. 2011. Vol. 48. P. 247-268.

### 2010^{1}

*International Journal of Heat and Mass Transfer*. 2010. Vol. 53. No. 23-24. P. 5298-5307.

### 2009^{1}

*International Journal of Multiphase Flow*. 2009. Vol. 35. No. 7. P. 650-660.

### Conferences

Papers in refereed international conferences 1. BB and M. Zimand. Linear list-approximation for short programs (or the power of a few random bits). In the 29th Conference on Computational Complexity (CCC 2014), November 2013 2. BB. Asymmetry of the Kolmogorov complexity of online predicting odd and even bits. In the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 125–136, Dagstuhl, Germany, 2014 3. BB, A. Makhlin, N. Vereshchagin, and M. Zimand. Short lists with short programs in short time. In the 28th Conference on Computational Complexity (CCC 2013), June 2013 4. BB. Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), February 2012 5. BB. m-sophistication. In Proceedings of the 6th Conference on Computability in Europe (CiE 2010), July 2010 6. D. Devlaminck, W. Waegeman, BB, B. Wyns, G. Otte, and P. Santens. From circular ordinal regression to multilabel classification. In ECML 2010 Workshop on Preference Learning, Barcelona, Spain, September 2010 7. D. Devlaminck, W. Waegeman, B.Bauwens, B.Wyns, G.Otte, L.Boullart, and P.Santens. Directional predictions for 4-class bci data. In Proceedings of the 18th conference on Artificial Neural Networks, Computational intelligence, and Machine learning, pages 153–158, Brugge, April 2009 8. H. Cani`ere, BB, C. T’Joen, L. Boullart, and M. De Paepe. Classification of horizontal two-phase flow using support vector machines with capacitance signals. In Proceedings of the IIR International Congress of Refrigeration, pages 21–26, 2007 9. H. Cani`ere, BB, C. T’Joen, A. Willockx, L. Boullart, and M. De Paepe. Horizontal two-phase flow characterisation and classification based on capacitance measurements. In Proceedings of the 5th International Conference on Heat Transfer, Fluid Mechanics and Thermodynamics, 2007 10. BB, B. Wyns, D. Devlaminck, G. Otte, L. Boullart, and P. Santens. Mutual information and algorithmic information transfer as ideal undirected and directed independence tests. In Proceedings of the 2007 International Conference on Foundations of Computer Science, LasVegas, 2007 11. BB, B. Wyns, D. Devlaminck, G. Otte, L. Boullart, and P. Santens. Measuring instantaneous directed dependencies in interacting oscillators. In Proceedings of the 28th Symposium on Information Theory

### Grants

Causality between EEG and deep brain signals, theory and application: Phd grant for Flanders Institute for Technology and Innovation.

Design educational interactive applets for exercises in mathematical analysis: grant from the science education fund (10 000 euro).

Kolmogorov complexity, induction and applications to probabilistic inductive logical programming: a grant from the Portuguese Science Foundation (20 000 euro).

### Employment history

Teaching 2/2006-8/2008 Introduction to computer science for medical engineers, signal processing part (both theory and exercises) Spring 2009 Probability and statistics for civil engineers, exercises 2/2010-6/2011 Teaching assistant (help with exercises, theory, and study attitude) for freshmen: basic mathematics, analysis, algebra, geometry, physics in the faculty of engineering and architecture, all physics courses in the faculty of sciences 2/2014-4/2014 Physics in high school Sint-Pieterscollege (highest grade, in classes focussed on science and math) 6/2014– Co-lecturer for the course “Complexity and Computability” Teaching assistant for the course “Programming in Python” 10/2014–11/2014 Interim replacement of a lecturer mathematics (teaching pre-calculus and calculus to students in the major of commercial sciences) 11/2015–5/2016 Theoretical computer science to Phd students

## 'I’m impressed by the mathematical history and general level of mathematical skills here in Moscow'

Bruno Bauwens, an expert in Kolmogorov complexity, is a new recruit at the HSE Faculty of Computer Science. He started in September 2015. Bruno received his PhD from Ghent University in Belgium, after which he held postdoctoral fellowships at Porto University (Portugal), as well as at the University of Montpellier and University of Lorraine.

## International Experts in the Faculty of Computer Science

An important step in integrating the university into the global educational, scientific and research space is the expansion of international recruiting. Since its very first year, the Faculty of Computer Science at the Higher School of Economics has had a foreign professor working on staff. In 2015, four internationally recruited experts teach and conduct research in the faculty.

## International Experts in the Faculty of Computer Science

An important step in integrating the university into the global educational, scientific and research space is the expansion of international recruiting. Since its very first year, the Faculty of Computer Science at the Higher School of Economics has had a foreign professor working on staff. In 2015, four internationally recruited experts teach and conduct research in the faculty.