Conferences · eligible papers
STOC
2021–2025 確定版
2023 · 155 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
日本大学: 関与なし（対象大学）
- A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
日本大学: 関与なし（対象大学）
- A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
日本大学: 関与なし（対象大学）
- A Characterization of List Learnability
日本大学: 関与なし（対象大学）
- A Constant Factor Prophet Inequality for Online Combinatorial Auctions
日本大学: 関与なし（対象大学）
- A Duality between One-Way Functions and Average-Case Symmetry of Information
日本大学: 東京科学大学
- A High Dimensional Goldreich-Levin Theorem
日本大学: 関与なし（対象大学）
- A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
日本大学: 関与なし（対象大学）
- A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
日本大学: 関与なし（対象大学）
- A New Approach to Learning Linear Dynamical Systems
日本大学: 関与なし（対象大学）
- A New Berry-Esseen Theorem for Expander Walks
日本大学: 関与なし（対象大学）
- A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
日本大学: 関与なし（対象大学）
- A PTAS for Minimizing Weighted Flow Time on a Single Machine
日本大学: 関与なし（対象大学）
- A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
日本大学: 関与なし（対象大学）
- A Proof of the Nisan-Ronen Conjecture
日本大学: 関与なし（対象大学）
- A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
日本大学: 関与なし（対象大学）
- A Unified Framework for Light Spanners
日本大学: 関与なし（対象大学）
- A Unifying Theory of Distance from Calibration
日本大学: 関与なし（対象大学）
- Algorithmic Applications of Hypergraph and Partition Containers
日本大学: 関与なし（対象大学）
- Algorithms Approaching the Threshold for Semi-random Planted Clique
日本大学: 関与なし（対象大学）
- Almost Chor-Goldreich Sources and Adversarial Random Walks
日本大学: 関与なし（対象大学）
- Almost-Optimal Sublinear Additive Spanners
日本大学: 関与なし（対象大学）
- An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
日本大学: 関与なし（対象大学）
- An Efficient Decoder for a Linear Distance Quantum LDPC Code
日本大学: 関与なし（対象大学）
- An Improved Approximation Guarantee for Prize-Collecting TSP
日本大学: 関与なし（対象大学）
- An Improved Parameterized Algorithm for Treewidth
日本大学: 関与なし（対象大学）
- An Optimal “It Ain’t Over Till It’s Over” Theorem
日本大学: 関与なし（対象大学）
- Approximate Distance Sensitivity Oracles in Subquadratic Space
日本大学: 関与なし（対象大学）
- Approximate Graph Colouring and the Hollow Shadow
日本大学: 関与なし（対象大学）
- Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
日本大学: 関与なし（対象大学）
- Approximating Binary Longest Common Subsequence in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Approximating Iterated Multiplication of Stochastic Matrices in Small Space
日本大学: 関与なし（対象大学）
- Approximating Nash Social Welfare by Matching and Local Search
日本大学: 関与なし（対象大学）
- Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
日本大学: 関与なし（対象大学）
- Better Trees for Santa Claus
日本大学: 関与なし（対象大学）
- Binary Error-Correcting Codes with Minimal Noiseless Feedback
日本大学: 関与なし（対象大学）
- Boosting Batch Arguments and RAM Delegation
日本大学: 関与なし（対象大学）
- Capturing One-Way Functions via NP-Hardness of Meta-Complexity
日本大学: 関与なし（対象大学）
- Certified Randomness from Quantum Supremacy
日本大学: 関与なし（対象大学）
- Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
日本大学: 関与なし（対象大学）
- Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
日本大学: 関与なし（対象大学）
- Commitments to Quantum States
日本大学: 関与なし（対象大学）
- Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
日本大学: 関与なし（対象大学）
- Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
日本大学: 関与なし（対象大学）
- Concurrent Composition Theorems for Differential Privacy
日本大学: 関与なし（対象大学）
- Constant-Round Arguments from One-Way Functions
日本大学: 関与なし（対象大学）
- Credible Decentralized Exchange Design via Verifiable Sequencing Rules
日本大学: 関与なし（対象大学）
- Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
日本大学: 関与なし（対象大学）
- Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
日本大学: 関与なし（対象大学）
- Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester
日本大学: 関与なし（対象大学）
- Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
日本大学: 関与なし（対象大学）
- Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set
日本大学: 関与なし（対象大学）
- Dynamic Maxflow via Dynamic Interior Point Methods
日本大学: 関与なし（対象大学）
- Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
日本大学: 関与なし（対象大学）
- Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
日本大学: 関与なし（対象大学）
- External Memory Fully Persistent Search Trees
日本大学: 関与なし（対象大学）
- Extractors for Images of Varieties
日本大学: 関与なし（対象大学）
- Fast Algorithms via Dynamic-Oracle Matroids
日本大学: 関与なし（対象大学）
- Faster Deterministic Distributed MIS and Approximate Matching
日本大学: 関与なし（対象大学）
- Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
日本大学: 関与なし（対象大学）
- Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
日本大学: 関与なし（対象大学）
- Finding a Small Vertex Cut on Distributed Networks
日本大学: 関与なし（対象大学）
- First-Order Model Checking on Structurally Sparse Graph Classes
日本大学: 関与なし（対象大学）
- Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
日本大学: 関与なし（対象大学）
- Generic Reed-Solomon Codes Achieve List-Decoding Capacity
日本大学: 関与なし（対象大学）
- Good Quantum LDPC Codes with Linear Time Decoders
日本大学: 関与なし（対象大学）
- Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
日本大学: 関与なし（対象大学）
- Hardness Self-Amplification: Simplified, Optimized, and Unified
日本大学: 東京科学大学
- Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
日本大学: 関与なし（対象大学）
- Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
日本大学: 関与なし（対象大学）
- Improved Dynamic Colouring of Sparse Graphs
日本大学: 関与なし（対象大学）
- Improved and Deterministic Online Service with Deadlines or Delay
日本大学: 関与なし（対象大学）
- Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
日本大学: 関与なし（対象大学）
- Interior Point Methods with a Gradient Oracle
日本大学: 関与なし（対象大学）
- Kneser Graphs Are Hamiltonian
日本大学: 関与なし（対象大学）
- Lattice Problems beyond Polynomial Time
日本大学: 関与なし（対象大学）
- Learning Polynomial Transformations via Generalized Tensor Decompositions
日本大学: 関与なし（対象大学）
- Lifting Uniform Learners via Distributional Decomposition
日本大学: 関与なし（対象大学）
- Linear Independence, Alternants, and Applications
日本大学: 関与なし（対象大学）
- Local and Global Expansion in Random Geometric Graphs
日本大学: 関与なし（対象大学）
- Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
日本大学: 関与なし（対象大学）
- Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
日本大学: 関与なし（対象大学）
- Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
日本大学: 関与なし（対象大学）
- Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
日本大学: 関与なし（対象大学）
- Multi-agent Contracts
日本大学: 関与なし（対象大学）
- Multidimensional Quantum Walks
日本大学: 関与なし（対象大学）
- NLTS Hamiltonians from Good Quantum Codes
日本大学: 関与なし（対象大学）
- NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
日本大学: 関与なし（対象大学）
- Near-Optimal Derandomization of Medium-Width Branching Programs
日本大学: 関与なし（対象大学）
- Nearly All 𝑘-SAT Functions Are Unate
日本大学: 関与なし（対象大学）
- New Algorithms for All Pairs Approximate Shortest Paths
日本大学: 関与なし（対象大学）
- New High Dimensional Expanders from Covers
日本大学: 関与なし（対象大学）
- New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
日本大学: 関与なし（対象大学）
- Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
日本大学: 関与なし（対象大学）
- Obfuscation of Pseudo-Deterministic Quantum Circuits
日本大学: 関与なし（対象大学）
- On Approximability of Satisfiable k-CSPs: II
日本大学: 関与なし（対象大学）
- On Approximability of Satisfiable k-CSPs: III
日本大学: 関与なし（対象大学）
- On Regularity Lemma and Barriers in Streaming and Dynamic Matching
日本大学: 関与なし（対象大学）
- On the Consistency of Circuit Lower Bounds for Non-deterministic Time
日本大学: 関与なし（対象大学）
- On the Optimal Fixed-Price Mechanism in Bilateral Trade
日本大学: 関与なし（対象大学）