# Publications

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 (http://kth.diva-portal.org/) or KTHB (https://www.kth.se/kthb).

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

## Most recent publications

[1]

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.
[2]

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.
[3]

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.
[4]

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.
[5]

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.
[6]

P. Austrin

*et al.*, "On the Impossibility of Cryptography with Tamperable Randomness,"*Algorithmica*, vol. 79, no. 4, pp. 1052-1101, 2017.
[7]

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.
[8]

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.
[9]

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.
[10]

J. Alwen

*et al.*, "Cumulative Space in Black-White Pebbling and Resolution," in*Leibniz International Proceedings in Informatics, LIPIcs*, 2017.
[11]

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.
[12]

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.
[13]

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.
[14]

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.
[15]

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.
[16]

"Proceedings of the 2017 European Intelligence and Security Informatics Conference (EISIC 2017),"
Piscataway, New Jersey, IEEE, 2017.

[17]

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.
[18]

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.
[19]

J. Westman

*et al.*, "Formal Architecture Modeling of Sequential Non-Recursive C Programs,"*Science of Computer Programming*, vol. 146, pp. 2-27, 2017.
[20]

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.
[21]

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.
[22]

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.
[23]

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.
[24]

J. Håstad and R. Manokaran,
"On the Hardness of Approximating Balanced Homogeneous 3-Lin,"

*Theory of Computing*, vol. 13, 2017.
[25]

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.
[26]

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.
[27]

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.
[28]

G. Gkotsis

*et al.*, "Characterisation of mental health conditions in social media using Informed Deep Learning,"*Scientific Reports*, vol. 7, 2017.
[29]

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.
[30]

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.
[31]

[32]

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.
[33]

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.
[34]

H. Nemati

*et al.*, "Formal Analysis of Countermeasures against Cache Storage Side Channels," (Manuscript).
[35]

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.
[36]

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.
[37]

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.
[38]

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.
[39]

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.
[40]

E. Kanoulas and J. Karlgren,
"Practical Issues in Information Access System Evaluation,"

*SIGIR Forum*, vol. 51, no. 1, pp. 67-72, 2017.
[41]

V. T. Vasconcelos and P. Haller,
"Preface,"

*Electronic Proceedings in Theoretical Computer Science*, vol. 246, 2017.
[42]

"Proceedings of the 8th ACM SIGPLAN International Symposium on Scala,"
New York, NY, USA, Association for Computing Machinery (ACM), 2017.

[43]

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.

[44]

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.
[45]

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.
[46]

M. Vinyals,
"Space in Proof Complexity,"
Doctoral thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:15, 2017.

[47]

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.
[48]

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.
[49]

C. Ansotegui

*et al.*, "Structure features for SAT instances classification,"*Journal of Applied Logic*, vol. 23, pp. 27-39, 2017.
[50]

M. Lauria

*et al.*, "The complexity of proving that a graph is Ramsey,"*Combinatorica*, vol. 37, no. 2, pp. 253-268, 2017.