Conferences · eligible papers
STOC
2022–2026 LIVE
2022 · 134 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (Fractional) online stochastic matching via fine-grained offline statistics
日本大学: 関与なし（対象大学）
- 3.1 <i>n</i> − <i>o</i> ( <i>n</i> ) circuit lower bounds for explicit functions
日本大学: 関与なし（対象大学）
- A PTAS for unsplittable flow on a path
日本大学: 関与なし（対象大学）
- A characterization of approximability for biased CSPs
日本大学: 関与なし（対象大学）
- A new framework for matrix discrepancy: partial coloring bounds via mirror descent
日本大学: 関与なし（対象大学）
- A strong version of Cobham’s theorem
日本大学: 関与なし（対象大学）
- A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
日本大学: 関与なし（対象大学）
- Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
日本大学: 関与なし（対象大学）
- Almost-linear <i>ε</i> -emulators for planar graphs
日本大学: 関与なし（対象大学）
- Almost-optimal sublinear-time edit distance in the low distance regime
日本大学: 関与なし（対象大学）
- An area law for 2d frustration-free spin systems
日本大学: 関与なし（対象大学）
- An extendable data structure for incremental stable perfect hashing
日本大学: 関与なし（対象大学）
- An improved approximation algorithm for the minimum <i>k</i> -edge connected multi-subgraph problem
日本大学: 関与なし（対象大学）
- Approximate counting and sampling via local central limit theorems
日本大学: 関与なし（対象大学）
- Approximate polymorphisms
日本大学: 関与なし（対象大学）
- Approximately efficient bilateral trade
日本大学: 関与なし（対象大学）
- Asymptotically good Quantum and locally testable classical LDPC codes
日本大学: 関与なし（対象大学）
- Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
日本大学: 関与なし（対象大学）
- Breaching the 2-approximation barrier for the forest augmentation problem
日本大学: 関与なし（対象大学）
- Breaking the <i> n <sup>k</sup> </i> barrier for minimum <i>k</i> -cut on simple graphs
日本大学: 関与なし（対象大学）
- Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
日本大学: 関与なし（対象大学）
- Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
日本大学: 関与なし（対象大学）
- Byzantine agreement in polynomial time with near-optimal resilience
日本大学: 関与なし（対象大学）
- Circuits resilient to short-circuit errors
日本大学: 関与なし（対象大学）
- Clustering mixture models in almost-linear time via list-decodable mean estimation
日本大学: 関与なし（対象大学）
- Clustering mixtures with almost optimal separation in polynomial time
日本大学: 関与なし（対象大学）
- Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders
日本大学: 関与なし（対象大学）
- Complexity classification of counting graph homomorphisms modulo a prime number
日本大学: 関与なし（対象大学）
- Computational complexity of the ground state energy density problem
日本大学: 関与なし（対象大学）
- Computational thresholds for the fixed-magnetization Ising model
日本大学: 関与なし（対象大学）
- Computing simple mechanisms: Lift-and-round over marginal reduced forms
日本大学: 関与なし（対象大学）
- Constant inapproximability for PPA
日本大学: 関与なし（対象大学）
- Counting small induced subgraphs with hereditary properties
日本大学: 関与なし（対象大学）
- Deniable encryption in a Quantum world
日本大学: 関与なし（対象大学）
- Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
日本大学: 名古屋大学
- Deterministic (1+ <i>𝜀</i> )-approximate maximum matching with poly(1/ <i>𝜀</i> ) passes in the semi-streaming model and beyond
日本大学: 関与なし（対象大学）
- Deterministic graph coloring in the streaming model
日本大学: 関与なし（対象大学）
- Deterministic massively parallel connectivity
日本大学: 関与なし（対象大学）
- Deterministic, near-linear <i>𝜀</i> -approximation algorithm for geometric bipartite matching
日本大学: 関与なし（対象大学）
- Directed flow-augmentation
日本大学: 関与なし（対象大学）
- Distributed Quantum inner product estimation
日本大学: 関与なし（対象大学）
- Distributed ∆-coloring plays hide-and-seek
日本大学: 関与なし（対象大学）
- Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
日本大学: 関与なし（対象大学）
- Dynamic suffix array with polylogarithmic queries and updates
日本大学: 関与なし（対象大学）
- Edge connectivity augmentation in near-linear time
日本大学: 関与なし（対象大学）
- Edge sampling and graph parameter estimation via vertex neighborhood accesses
日本大学: 関与なし（対象大学）
- Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
日本大学: 関与なし（対象大学）
- Entropic independence: optimal mixing of down-up random walks
日本大学: 関与なし（対象大学）
- Expanders via local edge flips in quasilinear time
日本大学: 関与なし（対象大学）
- Explainable <i>k</i> -means: don’t be greedy, plant bigger trees!
日本大学: 関与なし（対象大学）
- Explicit binary tree codes with sub-logarithmic size alphabet
日本大学: 関与なし（対象大学）
- Extractors for sum of two sources
日本大学: 関与なし（対象大学）
- Fast FPT-approximation of branchwidth
日本大学: 関与なし（対象大学）
- Fast rates for nonparametric online learning: from realizability to learning in games
日本大学: 関与なし（対象大学）
- Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
日本大学: 関与なし（対象大学）
- Faster maxflow via improved dynamic spectral vertex sparsifiers
日本大学: 関与なし（対象大学）
- Faster min-plus product for monotone instances
日本大学: 関与なし（対象大学）
- Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
日本大学: 関与なし（対象大学）
- Flow time scheduling and prefix Beck-Fiala
日本大学: 関与なし（対象大学）
- Hamiltonian complexity in the thermodynamic limit
日本大学: 関与なし（対象大学）
- Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
日本大学: 関与なし（対象大学）
- Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
日本大学: 関与なし（対象大学）
- Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
日本大学: 関与なし（対象大学）
- Hypercontractivity on high dimensional expanders
日本大学: 関与なし（対象大学）
- Hypercontractivity on high dimensional expanders
日本大学: 関与なし（対象大学）
- Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
日本大学: 関与なし（対象大学）
- Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios
日本大学: 関与なし（対象大学）
- Improved approximations for Euclidean <i>k</i> -means and <i>k</i> -median, via nested quasi-independent sets
日本大学: 関与なし（対象大学）
- Improved communication complexity of fault-tolerant consensus
日本大学: 関与なし（対象大学）
- Improved iteration complexities for overconstrained <i>p</i> -norm regression
日本大学: 関与なし（対象大学）
- Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption
日本大学: 関与なし（対象大学）
- Kalman filtering with adversarial corruptions
日本大学: 関与なし（対象大学）
- Learning general halfspaces with general Massart noise under the Gaussian distribution
日本大学: 関与なし（対象大学）
- Learning low-degree functions from a logarithmic number of random queries
日本大学: 関与なし（対象大学）
- Linear space streaming lower bounds for approximating CSPs
日本大学: 関与なし（対象大学）
- List-decodable covariance estimation
日本大学: 関与なし（対象大学）
- Locality-sensitive orderings and applications to reliable spanners
日本大学: 関与なし（対象大学）
- Locally testable codes with constant rate, distance, and locality
日本大学: 関与なし（対象大学）
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
日本大学: 関与なし（対象大学）
- Low-rank approximation with <i> 1/𝜖 <sup>1/3</sup> </i> matrix-vector products
日本大学: 関与なし（対象大学）
- Low-temperature Ising dynamics with random initializations
日本大学: 関与なし（対象大学）
- Maintaining exact distances under multiple edge failures
日本大学: 関与なし（対象大学）
- Matrix anti-concentration inequalities with applications
日本大学: 関与なし（対象大学）
- Matrix discrepancy from Quantum communication
日本大学: 関与なし（対象大学）
- Memory bounds for the experts problem
日本大学: 関与なし（対象大学）
- Near-optimal Quantum algorithms for multivariate mean estimation
日本大学: 関与なし（対象大学）
- Near-optimal distributed degree+1 coloring
日本大学: 関与なし（対象大学）
- Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games
日本大学: 関与なし（対象大学）
- Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
日本大学: 関与なし（対象大学）
- New streaming algorithms for high dimensional EMD and MST
日本大学: 関与なし（対象大学）
- No self-concordant barrier interior point method is strongly polynomial
日本大学: 関与なし（対象大学）
- Nonlocal games, compression theorems, and the arithmetical hierarchy
日本大学: 関与なし（対象大学）
- On approximability of satisfiable <i>k</i> -CSPs: I
日本大学: 関与なし（対象大学）
- On the complexity of CSP-based ideal membership problems
日本大学: 関与なし（対象大学）
- On the complexity of dynamic submodular maximization
日本大学: 関与なし（対象大学）
- On the complexity of two-party differential privacy
日本大学: 関与なし（対象大学）
- On the hardness of dominant strategy mechanism design
日本大学: 関与なし（対象大学）
- On the optimal time/space tradeoff for hash tables
日本大学: 関与なし（対象大学）
- Online edge coloring via tree recurrences and correlation decay
日本大学: 関与なし（対象大学）
- Optimal oblivious reconfigurable networks
日本大学: 関与なし（対象大学）