Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Zero-error expectation equals amortized query complexity
Daiki Suruga
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expect…
cs.CC2026
Zero-error information equals amortized communication complexity
Daiki Suruga
The direct sum problem in computational complexity asks whether solving independent instances of a computational task inherently requires times the resources needed to solv…
cs.CC2025
Direct sum theorems beyond query complexity
Daiki Suruga
A fundamental question in computer science is: Is it harder to solve instances independently than to solve them simultaneously? This question, known as the direct sum question…