Все публикации

0:24:37

STOC24 8 A 5 Black Box PPP is Not Turing Closed

0:57:56

TCS for All Inspiration Talk: Prof. Luca Trevisan

0:24:07

STOC24 7 A 5 Dynamic O(arboricity) coloring in polylogarithmic worst case time

0:16:57

STOC24 3 A 5 Better coloring of 3-colorable graphs

0:15:54

STOC24 11 A 1 Proof of the density threshold conjecture for pinwheel scheduling

0:15:15

STOC24 2 D 5 No Regret Learning in Bilateral Trade via Global Budget Balance

0:20:34

STOC24 3 C 4 Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice Based SNARKs

0:14:44

STOC24 5 A 5 Explicit two sided unique neighbor expanders

0:25:33

STOC24 2 B 1 Strong Algebras and Radical Sylvester Gallai Configurations

0:16:30

STOC24 4 B 2 Quantum and classical query complexities of functions of matrices

0:19:26

STOC24 6 D 1 Local geometry of NAE SAT solutions in the condensation regime

0:16:05

STOC24 11 D 3 Hardness Condensation by Restriction

0:24:34

STOC24 11 B 4 No distributed quantum advantage for approximate graph coloring

0:25:05

STOC24 3 A 1 0-1 Knapsack in Nearly Quadratic Time

0:25:51

STOC24 3 D 1 Approximating Maximum Matching Requires Almost Quadratic Time

0:24:20

STOC24 2 B 2 Black Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipo

0:25:19

STOC24 3 C 5 Batch Proofs are Statistically Hiding

0:23:19

STOC24 2 B 3 The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups

0:22:23

STOC24 11 C 2 Semidefinite programming and linear equations vs homomorphism problems

0:27:35

STOC24 3 D 2 Structural Complexities of Matching Mechanisms

0:25:09

STOC24 11 B 5 Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond

0:24:48

STOC24 3 D 3 A constant factor approximation for Nash social welfare with subadditive valuations

0:22:12

STOC24 11 C 1 Sum of Squares Lower Bounds for Independent Set on Ultra Sparse Random Graphs

0:20:04

STOC24 2 A 5 Maximum Bipartite Matching in n^{2+o(1)} Time via a Combinatorial Algorithm