TCS blog aggregator
@cstheory
Posts from the Theory of Computing Blog Aggregator maintained by @nimaanari, @abhatt2, and @thegautamkamath.
Logic and lack of Logic of Anti Vaxers ift.tt/1lfS3ep
GPT as an “Intelligence Forklift.” ift.tt/dYpTL9q
Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels ift.tt/8Bl3HkZ
On the approximability and energy-flow modeling of the electric vehicle sharing problem ift.tt/3XZGgRi
OPTWIN: Drift identification with optimal sub-windows ift.tt/modVieA
Distortion in metric matching with ordinal preferences ift.tt/FIpVXms
Perspective on complexity measures targetting read-once branching programs ift.tt/kunRTwh
Making $\textsf{IP}=\textsf{PSPACE}$ Practical: Efficient Interactive Protocols for BDD Algorithms ift.tt/ciSn37m
Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions ift.tt/5BpXov9
Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average-degrees ift.tt/Yg0QSwi
Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues ift.tt/s2rhdy0
Efficient quantum linear solver algorithm with detailed running costs ift.tt/6YQduSB
Approximate Distance Sensitivity Oracles in Subquadratic Space ift.tt/ZLMXvd9
Distributed MIS with Low Energy and Time Complexities ift.tt/iA7Go4W
Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ift.tt/jMNL4zY
Tester-Learners for Halfspaces: Universal Algorithms ift.tt/hUstdxw