Conferences · eligible papers
STOC
2022–2026 LIVE
2024 · 191 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- Nearly Optimal Fault Tolerant Distance Oracle
日本大学: 関与なし（対象大学）
- New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
日本大学: 関与なし（対象大学）
- New Graph and Hypergraph Container Lemmas with Applications in Property Testing
日本大学: 関与なし（対象大学）
- New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
日本大学: 関与なし（対象大学）
- No Complete Problem for Constant-Cost Randomized Communication
日本大学: 関与なし（対象大学）
- No Distributed Quantum Advantage for Approximate Graph Coloring
日本大学: 名古屋大学
- No-Regret Learning in Bilateral Trade via Global Budget Balance
日本大学: 関与なし（対象大学）
- Nonlinear Dynamics for the Ising Model
日本大学: 関与なし（対象大学）
- Nonlocality under Computational Assumptions
日本大学: 関与なし（対象大学）
- O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set
日本大学: 関与なし（対象大学）
- On Approximability of Satisfiable k-CSPs: IV
日本大学: 関与なし（対象大学）
- On Optimal Coreset Construction for Euclidean (k,z)-Clustering
日本大学: 関与なし（対象大学）
- On the Communication Complexity of Approximate Pattern Matching
日本大学: 関与なし（対象大学）
- On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
日本大学: 関与なし（対象大学）
- On the Pauli Spectrum of QAC0
日本大学: 関与なし（対象大学）
- On the Power of Homogeneous Algebraic Formulas
日本大学: 関与なし（対象大学）
- On the Power of Interactive Proofs for Learning
日本大学: 関与なし（対象大学）
- One-Way Functions and Zero Knowledge
日本大学: 東京科学大学
- Online Edge Coloring Is (Nearly) as Easy as Offline
日本大学: 関与なし（対象大学）
- Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL
日本大学: 関与なし（対象大学）
- Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
日本大学: 関与なし（対象大学）
- Optimal Embedding Dimension for Sparse Subspace Embeddings
日本大学: 関与なし（対象大学）
- Optimal Load-Balanced Scalable Distributed Agreement
日本大学: 関与なし（対象大学）
- Optimal Multi-pass Lower Bounds for MST in Dynamic Streams
日本大学: 関与なし（対象大学）
- Optimal Non-adaptive Tolerant Junta Testing via Local Estimators
日本大学: 関与なし（対象大学）
- Optimal Online Discrepancy Minimization
日本大学: 関与なし（対象大学）
- Optimization with Pattern-Avoiding Input
日本大学: 関与なし（対象大学）
- PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
日本大学: 関与なし（対象大学）
- Packing Even Directed Circuits Quarter-Integrally
日本大学: 東京大学
- Parallel Sampling via Counting
日本大学: 関与なし（対象大学）
- Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
日本大学: 関与なし（対象大学）
- Perfect Zero-Knowledge PCPs for #P
日本大学: 関与なし（対象大学）
- Planted Clique Conjectures Are Equivalent
日本大学: 東京科学大学
- Polylog-Competitive Deterministic Local Routing and Scheduling
日本大学: 関与なし（対象大学）
- Private Graphon Estimation via Sum-of-Squares
日本大学: 関与なし（対象大学）
- Prize-Collecting Steiner Tree: A 1.79 Approximation
日本大学: 関与なし（対象大学）
- Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
日本大学: 関与なし（対象大学）
- Product Mixing in Compact Lie Groups
日本大学: 関与なし（対象大学）
- Proof of the Density Threshold Conjecture for Pinwheel Scheduling
日本大学: 京都大学
- Prophet Inequalities Require Only a Constant Number of Samples
日本大学: 関与なし（対象大学）
- Prophet Inequalities with Cancellation Costs
日本大学: 関与なし（対象大学）
- Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
日本大学: 関与なし（対象大学）
- Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
日本大学: 関与なし（対象大学）
- Quantum State Obfuscation from Classical Oracles
日本大学: 関与なし（対象大学）
- Quantum Time-Space Tradeoffs for Matrix Problems
日本大学: 関与なし（対象大学）
- Quantum and Classical Query Complexities of Functions of Matrices
日本大学: 関与なし（対象大学）
- Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)
日本大学: 関与なし（対象大学）
- Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
日本大学: 関与なし（対象大学）
- Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
日本大学: 関与なし（対象大学）
- Reconfiguration of Basis Pairs in Regular Matroids
日本大学: 関与なし（対象大学）
- Relaxed Local Correctability from Local Testing
日本大学: 関与なし（対象大学）
- Revisiting Local Computation of PageRank: Simple and Optimal
日本大学: 関与なし（対象大学）
- Robust Recovery for Stochastic Block Models, Simplified and Generalized
日本大学: 関与なし（対象大学）
- SNARGs under LWE via Propositional Proofs
日本大学: 関与なし（対象大学）
- Sampling Balanced Forests of Grids in Polynomial Time
日本大学: 関与なし（対象大学）
- Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
日本大学: 総合研究大学院大学
- Self-Improvement for Circuit-Analysis Problems
日本大学: 関与なし（対象大学）
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems
日本大学: 関与なし（対象大学）
- Semidefinite Programs Simulate Approximate Message Passing Robustly
日本大学: 関与なし（対象大学）
- Semigroup Algorithmic Problems in Metabelian Groups
日本大学: 関与なし（対象大学）
- Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees
日本大学: 関与なし（対象大学）
- Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
日本大学: 関与なし（対象大学）
- Single-Source Shortest Paths with Negative Real Weights in <i> Õ(𝑚𝑛 <sup>8/9</sup> ) </i> Time
日本大学: 関与なし（対象大学）
- Solving Dense Linear Systems Faster Than via Preconditioning
日本大学: 関与なし（対象大学）
- Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
日本大学: 関与なし（対象大学）
- Sparsifying Generalized Linear Models
日本大学: 関与なし（対象大学）
- Strategic Budget Selection in a Competitive Autobidding World
日本大学: 関与なし（対象大学）
- Strong Algebras and Radical Sylvester-Gallai Configurations
日本大学: 関与なし（対象大学）
- Structural Complexities of Matching Mechanisms
日本大学: 関与なし（対象大学）
- Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
日本大学: 関与なし（対象大学）
- Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
日本大学: 関与なし（対象大学）
- Supermodular Approximation of Norms and Applications
日本大学: 関与なし（対象大学）
- Swap Cosystolic Expansion
日本大学: 関与なし（対象大学）
- Symmetric Exponential Time Requires Near-Maximum Circuit Size
日本大学: 関与なし（対象大学）
- Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
日本大学: 関与なし（対象大学）
- Testing Closeness of Multivariate Distributions via Ramsey Theory
日本大学: 関与なし（対象大学）
- The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True
日本大学: 関与なし（対象大学）
- The Complexity of Computing KKT Solutions of Quadratic Programs
日本大学: 関与なし（対象大学）
- The Computer in the Sky (Keynote)
日本大学: 関与なし（対象大学）
- The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups
日本大学: 関与なし（対象大学）
- The Power of Adaptivity in Quantum Query Algorithms
日本大学: 関与なし（対象大学）
- The Power of Two-Sided Recruitment in Two-Sided Markets
日本大学: 関与なし（対象大学）
- The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
日本大学: 関与なし（対象大学）
- Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
日本大学: 関与なし（対象大学）
- Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
日本大学: 関与なし（対象大学）
- Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
日本大学: 関与なし（対象大学）
- Trickle-Down in Localization Schemes and Applications
日本大学: 関与なし（対象大学）
- Two Prover Perfect Zero Knowledge for MIP*
日本大学: 関与なし（対象大学）
- Understanding the Cluster Linear Program for Correlation Clustering
日本大学: 関与なし（対象大学）
- Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
日本大学: 関与なし（対象大学）
- XOR Lemmas for Communication via Marginal Information
日本大学: 関与なし（対象大学）