Matthias Lanzinger

TU WIen Hauptgebäude

Hallo Bluesky-Community!
Die TU Wien teilt ab sofort spannende News zu Forschung und Wissenschaft hier auf Bluesky.
Bild c_Matthias Heisler

New paper: Simulating Time With Square-Root Space

people.csail.mit.edu/rrw/time-vs-...

It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].

To appear in STOC. Comments are very welcome!

The (soft) deadline for this position is on Friday.

Anyone want to start a betting pool on the % of #iclr meta-reviews that are fully LLM generated?

5/5
Finally, a prototype implementation demonstrates the practical impact on query evaluation. Early experiments show potential for large performance gains on difficult queries in standard database systems (e.g., PostgreSQL, SparkSQL)

Check it out: arxiv.org/pdf/2412.11669

4/
• SHW can achieve smaller widths than HW while remaining tractable to compute, boosting efficiency.
• SHW induces a hierarchy of width measures that equal generalised hypertree width in the limit.

3/ 🚀 Our contribution:
We propose Soft Hypertree Width (SHW) – a relaxed version of hypertree width that provides additional algorithmic flexibility, which allows for efficiently incorporating preferences and constraints into query decompositions.

2/ The problem: Theoretical performance of queries in databases depends on the "width" of decompositions of the query. The smaller the “width”, the more efficient evaluation is. But real-world performance isn’t just about the smallest width… constraints & preferences matter too!

1/ 📢 Excited to share our new paper: “Soft and Constrained Hypertree Width” – a step forward in optimizing database queries by introducing a flexible, and effective hypergraph decomposition framework. 🧵 arxiv.org/pdf/2412.11669

We use cookies to offer you the best possible website experience. Your cookie preferences will be stored in your browser’s local storage. This includes cookies necessary for the website's operation.

Open Tenure Track Positions at the University of Vienna! 👨‍🔬 👩‍🔬
#univie is currently accepting applications for several
#tenuretrack positions across a range of disciplines. 🧪 🏛
Work with us to find answers to the questions for tomorrow. 🔍 ⤵ #academicsky
jobs.univie.ac.at/go/Tenure-Tr...

#5QW: Stefan Neumann “It’s important to understand networks in terms of what’s going on within them and how they influence our behaviors, relationships, and societal structures.”

Happy to share my recent interview with TU Wien Informatics, where I discuss algorithms, social network analysis, and the beauty of theoretical computer science.

Check it out here: informatics.tuwien.ac.at/news/2713

#TCS #Algorithms #SocialNetworks

The PCP theorem, a jewel of theoretical computer science, establishes that any NP statement can be assessed by a randomized verifier who only checks a vanishing fraction of the proof (indeed, a constant # of characters!)

This has had incredible impact, most notably on how ML reviews are conducted

Homomorphism Counts as Structural Encodings for Graph Learning Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorp...

Also more recently arxiv.org/abs/2410.18676 :)

Emily and I have been working towards this moment for years. Two big papers just to set up one obscure reference to 90s hip-hop. Feeling proud to have finally achieved it.