Conferences · eligible papers
STOC
2021–2025 確定版
2021 · 151 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
日本大学: 関与なし（対象大学）
- Optimal testing of discrete distributions with high probability
日本大学: 関与なし（対象大学）
- Outcome indistinguishability
日本大学: 関与なし（対象大学）
- Perfectly sampling <i>k</i> ≥ (8/3 + <i>o</i> (1))Δ-colorings in graphs
日本大学: 関与なし（対象大学）
- Playing unique games on certified small-set expanders
日本大学: 関与なし（対象大学）
- Polynomial time deterministic identity testing algorithm for Σ <sup>[3]</sup> ΠΣΠ <sup>[2]</sup> circuits via Edelstein–Kelly type theorem for quadratic polynomials
日本大学: 関与なし（対象大学）
- Pseudodeterministic algorithms and the structure of probabilistic time
日本大学: 関与なし（対象大学）
- Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits
日本大学: 関与なし（対象大学）
- Reducing isotropy and volume to KLS: an <i>o</i> *( <i>n</i> <sup>3</sup> <i>ψ</i> <sup>2</sup> ) volume algorithm
日本大学: 関与なし（対象大学）
- Revelation gap for pricing from samples
日本大学: 関与なし（対象大学）
- Robust linear regression: optimal rates in polynomial time
日本大学: 関与なし（対象大学）
- Robust testing of low dimensional functions
日本大学: 関与なし（対象大学）
- SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
日本大学: 関与なし（対象大学）
- Sample-efficient proper PAC learning with approximate differential privacy
日本大学: 関与なし（対象大学）
- Sample-optimal and efficient learning of tree Ising models
日本大学: 関与なし（対象大学）
- Sampling constraint satisfaction solutions in the local lemma regime
日本大学: 関与なし（対象大学）
- Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacy
日本大学: 東京大学
- Separating words and trace reconstruction
日本大学: 関与なし（対象大学）
- Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
日本大学: 関与なし（対象大学）
- Settling the complexity of Nash equilibrium in congestion games
日本大学: 関与なし（対象大学）
- Settling the robust learnability of mixtures of Gaussians
日本大学: 関与なし（対象大学）
- Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
日本大学: 関与なし（対象大学）
- Simplicity creates inequity: implications for fairness, stereotypes, and interpretability (invited paper)
日本大学: 関与なし（対象大学）
- Sparse nonnegative convolution is equivalent to dense nonnegative convolution
日本大学: 関与なし（対象大学）
- Statistical physics of random CSPs (tutorial)
日本大学: 関与なし（対象大学）
- Statistical query complexity of manifold estimation
日本大学: 関与なし（対象大学）
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
日本大学: 関与なし（対象大学）
- Stronger bounds for weak epsilon-nets in higher dimensions
日本大学: 関与なし（対象大学）
- Stronger calibration lower bounds via sidestepping
日本大学: 関与なし（対象大学）
- Structure vs. randomness for bilinear maps
日本大学: 関与なし（対象大学）
- Subcubic algorithms for Gomory–Hu tree in unweighted graphs
日本大学: 関与なし（対象大学）
- Succinct blind Quantum computation using a random oracle
日本大学: 関与なし（対象大学）
- Support of closed walks and second eigenvalue multiplicity of graphs
日本大学: 関与なし（対象大学）
- The communication complexity of multiparty set disjointness under product distributions
日本大学: 関与なし（対象大学）
- The communication complexity of payment computation
日本大学: 関与なし（対象大学）
- The complexity of constrained min-max optimization
日本大学: 関与なし（対象大学）
- The complexity of gradient descent: CLS = PPAD ∩ PLS
日本大学: 関与なし（対象大学）
- The ghost in the radiation: robust encodings of the black hole interior (invited paper)
日本大学: 関与なし（対象大学）
- The limits of pan privacy and shuffle privacy for learning and estimation
日本大学: 関与なし（対象大学）
- The metric relaxation for <i>0</i> -extension admits an <i> Ω(log <sup>2/3</sup> k) </i> gap
日本大学: 関与なし（対象大学）
- The randomized communication complexity of randomized auctions
日本大学: 関与なし（対象大学）
- Tight conditional lower bounds for approximating diameter in directed graphs
日本大学: 関与なし（対象大学）
- Towards tight bounds for spectral sparsification of hypergraphs
日本大学: 関与なし（対象大学）
- Tree embeddings for hop-constrained network design
日本大学: 関与なし（対象大学）
- Universally-optimal distributed algorithms for known topologies
日本大学: 関与なし（対象大学）
- VC dimension and distribution-free sample-based testing
日本大学: 関与なし（対象大学）
- Vertex connectivity in poly-logarithmic max-flows
日本大学: 関与なし（対象大学）
- Vertex deletion parameterized by elimination distance and even less
日本大学: 関与なし（対象大学）
- When is approximate counting for conjunctive queries tractable?
日本大学: 関与なし（対象大学）
- When is memorization of irrelevant training data necessary for high-accuracy learning?
日本大学: 関与なし（対象大学）
- k-forrelation optimally separates Quantum and classical query complexity
日本大学: 関与なし（対象大学）