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

P. Austrin, V. Guruswami and J. Håstad, "(2 + ϵ)-SAT is NP-hard," SIAM journal on computing (Print), 46(5), 1554-1573.
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.
B. Bukh, V. Guruswami and J. Håstad, "An Improved Bound on the Fraction of Correctable Deletions," IEEE Transactions on Information Theory, 63(1), 93-103.
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 questions," in 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2017 - Proceedings of the Software Demonstrations, 2017, pp. 1-4.
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.
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.
J. Westman et al., "Formal Architecture Modeling of Sequential Non-Recursive C Programs," Science of Computer Programming, 146, 2-27.
C. Artho and P. C. Olveczky, "Formal Techniques for Safety-Critical Systems (FTSCS 2014) Preface," Science of Computer Programming, 133, 89-90.
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, 17(1).
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.
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, 79(4), 1052-1101.
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, 79(4), 1052-1101.
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, 51(1), 67-72.
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.
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, 79(1), 29-41.
C. Ansotegui et al., "Structure features for SAT instances classification," Journal of Applied Logic, 23, 27-39.
V. Guruswami et al., "SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES," SIAM journal on computing (Print), 46(1), 132-159.
M. Lauria et al., "The complexity of proving that a graph is Ramsey," Combinatorica, 37(2), 253-268.
B. Greschbach et al., "The Effect of DNS on Tor’s Anonymity," in Network and Distributed System Security (NDSS) Symposium 2017, 2017.
G. Rodríguez-Cano, "Toward Privacy-Preserving Decentralised Systems," Licentiate thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:12, 2017.
P. Haller and F. Sommar, "Towards an Empirical Study of Affine Types for Isolated Actors in Scala," Electronic Proceedings in Theoretical Computer Science(246), 3-9.
M. García Lozano, J. Schreiber and J. Brynielsson, "Tracking Geographical Locations using a Geo-Aware Topic Model for Analyzing Social Media Data," Decision Support Systems, 99(SI), 18-29.
J. Andersson-Schwarz et al., "Transaktionsdimman på nätet hotar digitaliseringen," Dagens Nyheter.
M. Henzinger, S. Krinninger and D. Na Nongkai, "A deterministic almost-tight distributed algorithm for approximating single-source shortest paths," in Proceedings of the Annual ACM Symposium on Theory of Computing, 2016, pp. 489-498.
C. Baumann et al., "A High Assurance Virtualization Platform for ARMv8," in Networks and Communications (EuCNC), 2016 European Conference on, 2016.
R. Guanciale and E. Tuosto, "An Abstract Semantics of the Global View of Choreographies," in Proceedings 9th Interaction and Concurrency Experience, 2016.
J. Håstad, "An Average-case Depth Hierarchy Theorem for Higher Depths," in 2016 IEEE 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016, pp. 79-88.
A. Kohan, M. Yamamoto and C. Artho, "Automated Dataset Construction from Web Resources with Tool Kayur," in Proceedings - 2016 4th International Symposium on Computing and Networking, CANDAR 2016, 2016, pp. 98-104.
O. Schwarz and M. Dam, "Automatic Derivation of Platform Noninterference Properties," in Software Engineering and Formal Methods, Springer LNCS 9763, 2016, pp. 27-44.
P. Austrin, S. Benabbas and K. Georgiou, "Better Balance by Being Biased : A 0.8776-Approximation for Max Bisection," ACM Transactions on Algorithms, 13(1).
P. Austrin, S. Benabbas and K. Georgiou, "Better Balance by Being Biased : A 0.8776-Approximation for Max Bisection," ACM Transactions on Algorithms, 13(1).
V. Kann, "Blir studenternas språk sämre?," in Proc. Sixth Swedish Language Technology Conference, 2016.
R. Boppana et al., "Bounded Independence vs. Moduli," in Leibniz International Proceedings in Informatics, LIPIcs, 2016.
Full list in the KTH publications portal
Top page top