We present the 50 most recent publications by the Division of Theoretical Computer Science. If you are interested in older publications, please use KTH DiVA ( or KTHB (

Link to the full list   in the KTH publication portal here and in the bottom of the list.

Most recent publications

M. Lauria et al., "CNFgen : A generator of crafted benchmarks," in 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017, 2017, pp. 464-473.
H. Khosrowjerdi, K. Meinke and A. Rasmusson, "Learning-based testing for safety critical automotive applications," in 5th International Symposium on Model-Based Safety and Assessment, IMBSA 2017, 2017, pp. 197-211.
K. Meinke, "Learning-Based testing of cyber-physical systems-of-systems : A platooning study," in 14th European Workshop on Computer Performance Engineering, EPEW 2017, 2017, pp. 135-151.
L. Wiener, T. Ekholm and P. Haller, "Modular responsive web design : An experience report," in Companion to the first International Conference on the Art, Science and Engineering of Programming, 2017.
G. Papoudakis, P. Preux and M. Monperrus, "A generative model for sparse, evolving digraphs," in 6th International Conference on Complex Networks and Their Applications, Complex Networks 2017, 2018, pp. 531-542.
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, vol. 79, no. 4, pp. 1052-1101, 2017.
P. Austrin, V. Guruswami and J. Håstad, "(2 + ϵ)-SAT is NP-hard," SIAM journal on computing (Print), vol. 46, no. 5, pp. 1554-1573, 2017.
S. Khazaei and D. Wikström, "Return code schemes for electronic voting systems," in 2nd International Joint Conference on Electronic Voting, E-Vote-ID 2017, 2017, pp. 198-209.
D. Wikström et al., "How could Snowden attack an election?," in 2nd International Joint Conference on Electronic Voting, E-Vote-ID 2017, 2017, pp. 280-291.
J. Alwen et al., "Cumulative Space in Black-White Pebbling and Resolution," in Leibniz International Proceedings in Informatics, LIPIcs, 2017.
P. Chalermsook et al., "From Gap-ETH to FPT-Inapproximability : Clique, Dominating Set, and More," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 743-754.
M. Henzinger, S. Krinninger and D. Nanongkai, "Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks," ACM Transactions on Algorithms, vol. 13, no. 4, 2017.
C.-C. Huang, D. Na Nongkai and T. Saranurak, "Distributed Exact Weighted All-Pairs Shortest Paths in (O)over-tilde(n(5/4)) Rounds," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 168-179.
D. Na Nongkai, T. Saranurak and C. Wulff-Nilsen, "Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 950-961.
D. Nanongkai and T. Saranurak, "Dynamic spanning forest with worst-case update time : Adaptive, las vegas, and O(n1/2-∈) - Time," in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 1122-1129.
M. Sahlgren et al., "The Smart Data Layer," in Papers from the 2018 AAAI Spring Symposium on Artificial Intelligence for the Internet of Everything, 2018.
D. Gurov et al., "Deductive Functional Verification of Safety-Critical Embedded C-Code: An Experience Report," in Critical Systems: Formal Methods and Automated Verification, 2017, pp. 3-18.
J. Westman et al., "Formal Architecture Modeling of Sequential Non-Recursive C Programs," Science of Computer Programming, vol. 146, pp. 2-27, 2017.
B. Bukh, V. Guruswami and J. Håstad, "An Improved Bound on the Fraction of Correctable Deletions," IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 93-103, 2017.
M. Ekerå and J. Håstad, "Quantum algorithms for computing short discrete logarithms and factoring RSA integers," in 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017, 2017, pp. 347-363.
V. Guruswami et al., "SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES," SIAM journal on computing (Print), vol. 46, no. 1, pp. 132-159, 2017.
J. Håstad, "On small-depth Frege proofs for Tseitin for grids," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 97-108.
J. Håstad and R. Manokaran, "On the Hardness of Approximating Balanced Homogeneous 3-Lin," Theory of Computing, vol. 13, 2017.
I. Bastys, M. Balliu and A. Sabelfeld, "If This Then What? Controlling Flows in IoT Apps," in ACM Conference on Computer and Communications Security (CCS’18), 2018.
M. Amundin et al., "A proposal to use distributional models to analyse dolphin vocalization," in 1st International Workshop on Vocal Interactivity in-and-between Humans, Animals and Robots, 2017, 2017.
W. Oortwijn et al., "An Abstraction Technique for Describing Concurrent Program Behaviour," in 9th International Working Conference on Verified Software: Theories, Tools, and Experiments, VSTTE 2017, 2017, pp. 191-209.
T. Kitamura et al., "Classification tree method with parameter shielding," in 36th International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2017, 2017, pp. 230-241.
C. Baumann, O. Schwarz and M. Dam, "Compositional Verification of Security Properties for Embedded Execution Platforms," in PROOFS 2017 : 6th International Workshop on Security Proofs for Embedded Systems, 2017, pp. 1-16.
M. Minock, "COVER: Covering the Semantically Tractable Question," in Proceedings of the Software Demonstrations of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL), 2017.
M. Minock, "Evaluating an Automata Approach to Query Containment," in Proceedings of the 13th International Conference on Finite State Methods and Natural Language Processing (FSMNLP), 2017.
C. Artho and P. C. Olveczky, "Formal Techniques for Safety-Critical Systems (FTSCS 2014) Preface," Science of Computer Programming, vol. 133, pp. 89-90, 2017.
M. Lauria and J. Nordström, "Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases," in 32nd Computational Complexity Conference (CCC 2017), 2017.
E. Enström and V. Kann, "Iteratively Intervening with the “Most Difficult” Topics of an Algorithms and Complexity Course," ACM Transactions on Computing Education, vol. 17, no. 1, 2017.
G. Baud-Berthier, J. Giráldez-Cru and L. Simon, "On the community structure of bounded model checking SAT problems," in 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017, 2017, pp. 65-82.
M. Parks, J. Karlgren and S. Stymne, "Plausibility Testing for Lexical Resources," in Proceedings of CLEF 2017 : Information Access Evaluation meets Multilinguality, Multimodality, and Visualization, 2017.
E. Kanoulas and J. Karlgren, "Practical Issues in Information Access System Evaluation," SIGIR Forum, vol. 51, no. 1, pp. 67-72, 2017.
V. T. Vasconcelos and P. Haller, "Preface," Electronic Proceedings in Theoretical Computer Science, vol. 246, 2017.
"Proceedings of the 8th ACM SIGPLAN International Symposium on Scala," New York, NY, USA, Association for Computing Machinery (ACM), 2017.
H. Nemati, "Secure System Virtualization : End-to-End Verification of Memory Isolation," Doctoral thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:18, 2017.
F. Lemic et al., "Selection and aggregation of location information provisioning services," in 2017 26th International Conference on Computer Communications and Networks, ICCCN 2017, 2017.
R. Metere, A. Lindner and R. Guanciale, "Sound transpilation from binary to machine-independent code," in 20th Brazilian Symposium on Formal Methods, SBMF 2017, 2017, pp. 197-214.
M. Vinyals, "Space in Proof Complexity," Doctoral thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:15, 2017.
P. De Carvalho Gomes, D. Gurov and M. Huisman, "Specification and verification of synchronization with condition variables," in 5th International Workshop on Formal Techniques for Safety-Critical Systems, FTSCS 2016, 2017, pp. 3-19.
I. Bonacina and N. Talebanfard, "Strong ETH and Resolution via Games and the Multiplicity of Strategies," Algorithmica, vol. 79, no. 1, pp. 29-41, 2017.
C. Ansotegui et al., "Structure features for SAT instances classification," Journal of Applied Logic, vol. 23, pp. 27-39, 2017.
M. Lauria et al., "The complexity of proving that a graph is Ramsey," Combinatorica, vol. 37, no. 2, pp. 253-268, 2017.
Full list in the KTH publications portal
Page responsible:Web editors at EECS
Belongs to: Department of Theoretical Computer Science
Last changed: Apr 23, 2019