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

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

## TCS publications

[1]

P. Austrin, V. Guruswami and J. Håstad,
"(2 + ϵ)-SAT is NP-hard,"

*SIAM journal on computing (Print), 46*(5), 1554-1573.
[2]

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

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

G. Gkotsis

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

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

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

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

[9]

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

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

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

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

H. Nemati

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

J. Westman

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

C. Artho and P. C. Olveczky,
"Formal Techniques for Safety-Critical Systems (FTSCS 2014) Preface,"

*Science of Computer Programming, 133*, 89-90.
[16]

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

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

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

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

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

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

P. Austrin

*et al.*, "On the Impossibility of Cryptography with Tamperable Randomness,"*Algorithmica, 79*(4), 1052-1101.
[23]

P. Austrin

*et al.*, "On the Impossibility of Cryptography with Tamperable Randomness,"*Algorithmica, 79*(4), 1052-1101.
[24]

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

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

*SIGIR Forum, 51*(1), 67-72.
[26]

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

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

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.

[29]

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

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

[31]

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

I. Bonacina and N. Talebanfard,
"Strong ETH and Resolution via Games and the Multiplicity of Strategies,"

*Algorithmica, 79*(1), 29-41.
[33]

C. Ansotegui

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

V. Guruswami

*et al.*, "SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES,"*SIAM journal on computing (Print), 46*(1), 132-159.
[35]

M. Lauria

*et al.*, "The complexity of proving that a graph is Ramsey,"*Combinatorica, 37*(2), 253-268.
[36]

B. Greschbach

*et al.*, "The Effect of DNS on Tor’s Anonymity," in*Network and Distributed System Security (NDSS) Symposium 2017*, 2017.
[37]

G. Rodríguez-Cano,
"Toward Privacy-Preserving Decentralised Systems,"
Licentiate thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:12, 2017.

[38]

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

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

[41]

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

C. Baumann

*et al.*, "A High Assurance Virtualization Platform for ARMv8," in*Networks and Communications (EuCNC), 2016 European Conference on*, 2016.
[43]

R. Guanciale and E. Tuosto,
"An Abstract Semantics of the Global View of Choreographies,"
in

*Proceedings 9th Interaction and Concurrency Experience*, 2016.
[44]

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

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

O. Schwarz and M. Dam,
"Automatic Derivation of Platform Noninterference Properties,"
in

*Software Engineering and Formal Methods, Springer LNCS 9763*, 2016, pp. 27-44.
[47]

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

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

V. Kann,
"Blir studenternas språk sämre?,"
in

*Proc. Sixth Swedish Language Technology Conference*, 2016.
[50]

R. Boppana

*et al.*, "Bounded Independence vs. Moduli," in*Leibniz International Proceedings in Informatics, LIPIcs*, 2016.