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]
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.
[2]
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.
[3]
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.
[4]
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.
[5]
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.
[6]
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.
[8]
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.
[9]
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.
[10]
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.
[12]
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.
[13]
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.
[14]
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.
[15]
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.
[16]
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.
[17]
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.
[18]
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.
[20]
J. Westman et al., "Formal Architecture Modeling of Sequential Non-Recursive C Programs," Science of Computer Programming, vol. 146, pp. 2-27, 2017.
[21]
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.
[22]
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.
[23]
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.
[24]
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.
[25]
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.
[26]
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.
[27]
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.
[28]
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.
[29]
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.
[30]
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.
[31]
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, vol. 79, no. 4, pp. 1052-1101, 2017.
[32]
P. Austrin et al., "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, vol. 79, no. 4, pp. 1052-1101, 2017.
[33]
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.
[34]
E. Kanoulas and J. Karlgren, "Practical Issues in Information Access System Evaluation," SIGIR Forum, vol. 51, no. 1, pp. 67-72, 2017.
[35]
V. T. Vasconcelos and P. Haller, "Preface," Electronic Proceedings in Theoretical Computer Science, vol. 246, 2017.
[37]
"Proceedings of the 8th ACM SIGPLAN International Symposium on Scala," New York, NY, USA, Association for Computing Machinery (ACM), 2017.
[38]
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.
[39]
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.
[40]
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.
[41]
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.
[42]
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.
[43]
M. Vinyals, "Space in Proof Complexity," Doctoral thesis Stockholm : KTH Royal Institute of Technology, TRITA-CSC-A, 2017:15, 2017.
[44]
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.
[45]
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.
[46]
C. Ansotegui et al., "Structure features for SAT instances classification," Journal of Applied Logic, vol. 23, pp. 27-39, 2017.
[47]
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.
[48]
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.
[49]
M. Lauria et al., "The complexity of proving that a graph is Ramsey," Combinatorica, vol. 37, no. 2, pp. 253-268, 2017.
[50]
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