Posts from the Theory of Computing Blog Aggregator maintained by @nimaanari, @abhatt2, and @thegautamkamath.

Joined June 2010
Logic and lack of Logic of Anti Vaxers ift.tt/1lfS3ep
3,702
Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels ift.tt/8Bl3HkZ
1
5
3,194
On the approximability and energy-flow modeling of the electric vehicle sharing problem ift.tt/3XZGgRi
2,176
OPTWIN: Drift identification with optimal sub-windows ift.tt/modVieA
1,528
Distortion in metric matching with ordinal preferences ift.tt/FIpVXms
1
1,424
Making $\textsf{IP}=\textsf{PSPACE}$ Practical: Efficient Interactive Protocols for BDD Algorithms ift.tt/ciSn37m
3
2,292
Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions ift.tt/5BpXov9
1,225
Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average-degrees ift.tt/Yg0QSwi
1
1,265
Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues ift.tt/s2rhdy0
1,033
Efficient quantum linear solver algorithm with detailed running costs ift.tt/6YQduSB
1
972
Approximate Distance Sensitivity Oracles in Subquadratic Space ift.tt/ZLMXvd9
1
1,013
Distributed MIS with Low Energy and Time Complexities ift.tt/iA7Go4W
1
928
Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ift.tt/jMNL4zY
1
873
Tester-Learners for Halfspaces: Universal Algorithms ift.tt/hUstdxw
1
9
1,527