Conferences · eligible papers
STOC
2021–2025 確定版
2024 · 191 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (1 − <i>𝜀</i> )-Approximation of Knapsack in Nearly Quadratic Time
日本大学: 関与なし（対象大学）
- 0-1 Knapsack in Nearly Quadratic Time
日本大学: 関与なし（対象大学）
- A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations
日本大学: 関与なし（対象大学）
- A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications
日本大学: 関与なし（対象大学）
- A Flat Wall Theorem for Matching Minors in Bipartite Graphs
日本大学: 関与なし（対象大学）
- A Nearly Quadratic-Time FPTAS for Knapsack
日本大学: 関与なし（対象大学）
- A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
日本大学: 関与なし（対象大学）
- A New Information Complexity Measure for Multi-pass Streaming with Applications
日本大学: 関与なし（対象大学）
- A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography
日本大学: 関与なし（対象大学）
- A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture
日本大学: 関与なし（対象大学）
- A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column
日本大学: 関与なし（対象大学）
- A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
日本大学: 関与なし（対象大学）
- ACM Turing Award Lecture: Avi Wigderson
日本大学: 関与なし（対象大学）
- AG Codes Achieve List Decoding Capacity over Constant-Sized Fields
日本大学: 関与なし（対象大学）
- Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
日本大学: 関与なし（対象大学）
- Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers
日本大学: 関与なし（対象大学）
- Algorithmic Contract Design (Keynote)
日本大学: 関与なし（対象大学）
- Almost Linear Size Edit Distance Sketch
日本大学: 関与なし（対象大学）
- Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
日本大学: 関与なし（対象大学）
- Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth
日本大学: 関与なし（対象大学）
- An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP
日本大学: 関与なし（対象大学）
- An Efficient Quantum Parallel Repetition Theorem and Applications
日本大学: 関与なし（対象大学）
- An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
日本大学: 関与なし（対象大学）
- An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography
日本大学: 関与なし（対象大学）
- Approaching the Quantum Singleton Bound with Approximate Error Correction
日本大学: 関与なし（対象大学）
- Approximate Earth Mover’s Distance in Truly-Subquadratic Time
日本大学: 関与なし（対象大学）
- Approximating Maximum Matching Requires Almost Quadratic Time
日本大学: 関与なし（対象大学）
- Approximating Partition in Near-Linear Time
日本大学: 関与なし（対象大学）
- Approximating Small Sparse Cuts
日本大学: 関与なし（対象大学）
- Batch Proofs Are Statistically Hiding
日本大学: 関与なし（対象大学）
- Beating Brute Force for Compression Problems
日本大学: 関与なし（対象大学）
- Better Coloring of 3-Colorable Graphs
日本大学: 東京大学
- Bilateral Trade with Correlated Values
日本大学: 関与なし（対象大学）
- Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
日本大学: 関与なし（対象大学）
- Black-Box PPP Is Not Turing-Closed
日本大学: 関与なし（対象大学）
- Breaking the VLB Barrier for Oblivious Reconfigurable Networks
日本大学: 関与なし（対象大学）
- Calibrated Language Models Must Hallucinate
日本大学: 関与なし（対象大学）
- Characterizing Direct Product Testing via Coboundary Expansion
日本大学: 関与なし（対象大学）
- Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance
日本大学: 関与なし（対象大学）
- Classical Simulation of Peaked Shallow Quantum Circuits
日本大学: 関与なし（対象大学）
- Combinatorial Correlation Clustering
日本大学: 関与なし（対象大学）
- Commitments from Quantum One-Wayness
日本大学: 関与なし（対象大学）
- Communication Lower Bounds for Collision Problems via Density Increment Arguments
日本大学: 関与なし（対象大学）
- Complexity-Theoretic Implications of Multicalibration
日本大学: 関与なし（対象大学）
- Computing a Fixed Point of Contraction Maps in Polynomial Queries
日本大学: 関与なし（対象大学）
- Connectivity Labeling and Routing with Multiple Vertex Failures
日本大学: 関与なし（対象大学）
- Constant Query Local Decoding against Deletions Is Impossible
日本大学: 関与なし（対象大学）
- Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
日本大学: 関与なし（対象大学）
- Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
日本大学: 関与なし（対象大学）
- Counting Small Induced Subgraphs with Edge-Monotone Properties
日本大学: 関与なし（対象大学）
- Data-Dependent LSH for the Earth Mover’s Distance
日本大学: 関与なし（対象大学）
- Detecting Low-Degree Truncation
日本大学: 関与なし（対象大学）
- Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
日本大学: 関与なし（対象大学）
- Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
日本大学: 関与なし（対象大学）
- Edge-Disjoint Paths in Eulerian Digraphs
日本大学: 東京大学
- Equality Cases of the Alexandrov–Fenchel Inequality Are Not in the Polynomial Hierarchy
日本大学: 関与なし（対象大学）
- Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions
日本大学: 関与なし（対象大学）
- Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
日本大学: 関与なし（対象大学）
- Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication
日本大学: 関与なし（対象大学）
- Explicit Two-Sided Unique-Neighbor Expanders
日本大学: 関与なし（対象大学）
- Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
日本大学: 関与なし（対象大学）
- Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
日本大学: 関与なし（対象大学）
- Fair Division via Quantile Shares
日本大学: 関与なし（対象大学）
- Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria
日本大学: 関与なし（対象大学）
- Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
日本大学: 関与なし（対象大学）
- Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication
日本大学: 関与なし（対象大学）
- From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
日本大学: 関与なし（対象大学）
- Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
日本大学: 関与なし（対象大学）
- Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
日本大学: 関与なし（対象大学）
- Generalized GM-MDS: Polynomial Codes Are Higher Order MDS
日本大学: 関与なし（対象大学）
- Ghost Value Augmentation for k-Edge-Connectivity
日本大学: 関与なし（対象大学）
- Hardness Condensation by Restriction
日本大学: 関与なし（対象大学）
- Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
日本大学: 関与なし（対象大学）
- How Random CSPs Fool Hierarchies
日本大学: 関与なし（対象大学）
- How to Use Quantum Indistinguishability Obfuscation
日本大学: 関与なし（対象大学）
- Hypergraph Unreliability in Quasi-Polynomial Time
日本大学: 関与なし（対象大学）
- Improved Stabilizer Estimation via Bell Difference Sampling
日本大学: 関与なし（対象大学）
- Improving the Bit Complexity of Communication for Distributed Convex Optimization
日本大学: 関与なし（対象大学）
- Influences in Mixing Measures
日本大学: 関与なし（対象大学）
- Knapsack with Small Items in Near-Quadratic Time
日本大学: 関与なし（対象大学）
- Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
日本大学: 関与なし（対象大学）
- Learning Shallow Quantum Circuits
日本大学: 関与なし（対象大学）
- Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
日本大学: 関与なし（対象大学）
- Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
日本大学: 関与なし（対象大学）
- Limitations of Stochastic Selection Problems with Pairwise Independent Priors
日本大学: 関与なし（対象大学）
- Local Borsuk-Ulam, Stability, and Replicability
日本大学: 関与なし（対象大学）
- Local Correction of Linear Functions over the Boolean Cube
日本大学: 関与なし（対象大学）
- Local Geometry of NAE-SAT Solutions in the Condensation Regime
日本大学: 関与なし（対象大学）
- Local Minima in Quantum Systems
日本大学: 関与なし（対象大学）
- Locality Bounds for Sampling Hamming Slices
日本大学: 関与なし（対象大学）
- Low-Step Multi-commodity Flow Emulators
日本大学: 関与なし（対象大学）
- Lower Bounds for Regular Resolution over Parities
日本大学: 関与なし（対象大学）
- Maximum Bipartite Matching in 𝑛 <sup>2+𝑜(1)</sup> Time via a Combinatorial Algorithm
日本大学: 豊田工業大学
- Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
日本大学: 関与なし（対象大学）
- Memory Checking Requires Logarithmic Overhead
日本大学: 関与なし（対象大学）
- Minimum Star Partitions of Simple Polygons in Polynomial Time
日本大学: 関与なし（対象大学）
- Near Optimal Alphabet-Soundness Tradeoff PCPs
日本大学: 関与なし（対象大学）
- Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
日本大学: 関与なし（対象大学）
- Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
日本大学: 関与なし（対象大学）
- Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
日本大学: 豊田工業大学