STOC

2022–2026 LIVE

著者一覧 · 国際会議 · 大学ランキング

STOC 公式サイト ↗

Algorithms & Complexity

2026 · 211 papers

このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。

2026 · STOC
Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
Yang P. Liu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Instance-Optimal Quantum State Certification with Entangled Measurements
Ryan O'Donnell, Chirag Wadhwa
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity
Valentine Kabanets, Antonina Kolokolova
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations
Jon Kleinberg, Fan Wei
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime
Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Learning Read-Once Determinants and the Principal Minor Assignment Problem
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Learning Stabilizer Structure of Quantum States
Srinivasan Arunachalam, Arkopal Dutt
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Locally Computable High Independence Hashing
Yevgeniy Dodis, Shachar Lovett, Daniel Wichs
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Lower Bounds against the Ideal Proof System in Finite Fields
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Lower Bounds for Near-Quadratic-Depth Resolution over Parities
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Russell Impagliazzo
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, Tim Seppelt
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Lower Bounds on Flow Sparsifiers with Steiner Nodes
Yu Chen, Zihan Tan, Mingyang Yang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Lower Estimates for L₁-Distortion of Transportation Cost Spaces
Chris Gartland, Mikhail Ostrovskii
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
MIPᶜᵒ=coRE
Junqiao (Randy) Lin
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Magic and Communication Complexity
Uma Girish, Alex May, Natalie Parham, Henry Yuen
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Markov Chains Approximate Message Passing
Amit Rajaraman, David X. Wu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Memory Reallocation with Polylogarithmic Overhead
Ce Jin
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Mixing of General Biased Adjacent Transposition Chains
Reza Gheissari, Holden Lee, Eric Vigoda
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Monotone Circuit Complexity of Matching
Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Monte Carlo to Las Vegas for Recursively Composed Functions
Bandar Al-Dhalaan, Shalev Ben-David
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
NP-Membership for the Boundary-Boundary Art-Gallery Problem
Jack Stade
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, Ruilong Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Near Optimal Hardness of Approximating 𝑘-CSP
Dor Minzer, Kai Zhe Zheng
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Near-Optimal Directed Euclidean Spanners in High Dimensions
Rajesh Jayaram, Shyamal Patel, Clifford Stein, Erik Waingarten, Tian Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Negations Are Powerful Even in Small Depth
Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Jin-Yi Cai, Austen Fan, Shuai Shao, Zhuxiao Tang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
No Exponential Quantum Speedup for SIS∞ Anymore
Robin Kothari, Ryan O'Donnell, Kewen Wu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
Itai Dinur, Nathan Keller, Avichai Marmor
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Nonuniform Graph Partitioning with Just a Little Flex
Neil Olver, Harald Räcke, Stefan Schmid
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On Proximity Gaps of Reed-Solomon Codes
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On the Computational Hardness of Transformers
Barna Saha, Yinzhan Xu, Christopher Ye, Hantao Yu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On the Cryptographic Foundations of Interactive Quantum Advantage
Kabir Tomer, Mark Zhandry
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On the Informativeness of Moments in Optimal Stopping
José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, Jiechen Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
On the Need for (Quantum) Memory with Short Outputs
Zihan Hao, Zikuan Huang, Qipeng Liu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Online Combinatorial Optimization with Graphical Dependencies
Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, Sahil Singla
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
Aleksandar Nikolov, Haohua Tang, Jonathan Ullman
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Optimal Contest beyond Convexity
Negin Golrezaei, MohammadTaghi Hajiaghayi, Suho Shin
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Optimal Phylogenetic Reconstruction from Sampled Quartets
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
Rohan Goyal, Venkatesan Guruswami
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Optimal Random Self-Reductions for All Linear Problems
Shuichi Hirahara, Nobutaka Shimizu
Algorithms & Complexity
日本大学: 東京科学大学
2026 · STOC
Optimal and Efficient Partite Decompositions of Hypergraphs
Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, Bernardo Subercaseaux
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks
Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, Saket Saurabh
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Parallel Sampling via Autospeculation
Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, Thuy-Duong Vuong
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, Kirill Simonov
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Perfect Network Resilience in Polynomial Time
Matthias Bentert, Stefan Schmid
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Planar Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz, Richard Z Huang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System
Joshua A. Grochow
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Private Learning of Littlestone Classes, Revisited
Xin Lyu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Fernando Granha Jeronimo, Nikhil Shagrithaya
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Provable Long-Range Benefits of Next-Token Prediction
Xinyuan Cao, Santosh S. Vempala
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Quantum Circuit Lower Bounds in the Magic Hierarchy
Natalie Parham
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False
Adam Bene Watts, Charles R. Chen, J. William Helton, Joseph Slote
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Randomized Rounding over Dynamic Programs
Étienne Bamas, Shi Li, Lars Rohwedder
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Range Avoidance, Arthur-Merlin, and TFNP
Surendra Ghentiyala, Zeyong Li, Noah Stephens-Davidowitz
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In
Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Restriction Trees for Sparsity and Applications
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Reviving Thorup’s Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
S-Unit Equations in Modules and Linear-Exponential Diophantine Equations
Ruiwen Dong, Doron Shafrir
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
SNARGs for NP and Non-signaling PCPs, Revisited
Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, Surya Mathialagan
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
SNARKs from LWE via Non-black-Box Reductions
Zhengzhong Jin, Mingqi Lu, Bo Peng
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
SVP p Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of 2 log 1-ε n 
Isaac M. Hair, Amit Sahai
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, Qian Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sampling Permutations with Cell Probes Is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Secret-Key PIR from Random Linear Codes
Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein, Sahil Singla
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
Sepehr Assadi, Max Jiang, Mars Xiang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Separating QMA from QCMA with a Classical Oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tomáš Masařík
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Settling the Pass Complexity of Streaming Set Cover
Sepehr Assadi, Janani Sundaresan
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
Jason M. Altschuler, Sinho Chewi, Matthew S. Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li, Satish Rao, Junkai Zhang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions
Nir Bitansky, Saroja Erabelli, Rachit Garg, Yuval Ishai
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Smoothed Analysis of Learning from Positive Samples
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Solving Matrix Games with Near-Optimal Matvec Complexity
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Space-Efficient Text Indexing with Mismatches using Function Inversion
Jackson Bibbens, Levi Borevitz, Samuel McCauley
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sparse Linear Regression Is Easy on Random Supports
Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sparsifying Suprema of Gaussian Processes
Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta, Vera Traub
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Strong ETH Holds for Bounded-Depth Resolution over Parities
Klim Efremenko, Dmitry Itsykson
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sub-linear Secure Broadcast and Applications
Yuval Gelles, Ilan Komargodski, Merav Parter
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Maxime Flin, Magnús M. Halldórsson, Manuel Jakob, Yannic Maus
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
Lijie Chen, Avishay Tal, Yichuan Wang
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Testing Distributions against Bounded Distinguishers
Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr.
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
Testing Noisy Low-Degree Polynomials for Sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Nathan White
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
The Complexity of Min-Max Optimization with Product Constraints
Martino Bernasconi, Matteo Castiglioni
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography
Angelos Pelecanos, Jack Spilecki, John Wright
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
The Natural Proofs Barrier against Data-Structure Lower-Bounds
Michal Koucký, Bruno Loff, Tulasimohan Molli, Michael E. Saks
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
The Power of Two Bases: Robust and Copy-Optimal Certification of Nearly All Quantum States with Few-Qubit Measurements
Andrea Coladangelo, Jerry Li, Joseph Slote, Ellen Wu
Algorithms & Complexity
日本大学: 関与なし（対象大学）
2026 · STOC
The Price of Competitive Information Disclosure
Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, Kangning Wang
Algorithms & Complexity
日本大学: 関与なし（対象大学）