TCS 50 most recent publications

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

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

TCS publications

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.
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.
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.
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.
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.
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.
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.
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.
J. Alwen et al., "Cumulative Space in Black-White Pebbling and Resolution," in 8th Innovations in Theoretical Computer Science (ITCS) conference, Berkeley, January 9-11, 2017, 2017.
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.
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. 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.
J. Westman et al., "Formal Architecture Modeling of Sequential Non-Recursive C Programs," Science of Computer Programming, vol. 146, pp. 2-27, 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.
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. 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.
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.
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.
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 responsiveweb design : An experience report," in Proceeding Programming '17 Companion to the first International Conference on the Art, Science and Engineering of Programming, 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.
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.
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, vol. 79, no. 4, pp. 1052-1101, 2017.
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, vol. 79, no. 4, pp. 1052-1101, 2017.
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.
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.
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.
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. 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.
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.
M. Lauria et al., "The complexity of proving that a graph is Ramsey," Combinatorica, vol. 37, no. 2, pp. 253-268, 2017.
B. Greschbach et al., "The Effect of DNS on Tor’s Anonymity," in Network and Distributed System Security (NDSS) Symposium 2017, 2017.
Full list in the KTH publications portal
Top page top