hsfzLZH1's Homepage
2026
- Two-way finite automata: exponential costs of determinism and complement
- Shortest common superstring: assembling fragments within a factor of two
- Polynomial threshold functions: how often can one flipped bit change a decision?
- Exact Fourier transforms below n log n: the role of the arithmetic model
- Random graphs with prescribed degrees: a universal switch-chain mixing bound
- Sensitivity versus block sensitivity: beyond every quadratic bound
- Weisfeiler–Leman refinement: the cost of deciding what it can distinguish
- Generalized star height: three nested repetitions for every regular language
- PCP for PPAD: preserving a search problem despite many failed constraints
- One-tape computation: trading unrestricted time for two-fifths-power space