Conferences · eligible papers
STOC
2021–2025 確定版
2021 · 151 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem
日本大学: 関与なし（対象大学）
- A (2 + <i>ε</i> )-approximation algorithm for preemptive weighted flow time on a single machine
日本大学: 関与なし（対象大学）
- A (slightly) improved approximation algorithm for metric TSP
日本大学: 関与なし（対象大学）
- A deterministic algorithm for the MST problem in constant rounds of congested clique
日本大学: 関与なし（対象大学）
- A faster algorithm for solving general LPs
日本大学: 関与なし（対象大学）
- A framework for dynamic matching in weighted graphs
日本大学: 関与なし（対象大学）
- A framework for quadratic form maximization over convex sets through nonconvex relaxations
日本大学: 関与なし（対象大学）
- A full complexity dichotomy for immanant families
日本大学: 関与なし（対象大学）
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
日本大学: 関与なし（対象大学）
- A new algorithm for Euclidean shortest paths in the plane
日本大学: 関与なし（対象大学）
- A new analysis of differential privacy’s generalization guarantees (invited paper)
日本大学: 関与なし（対象大学）
- A new coreset framework for clustering
日本大学: 関与なし（対象大学）
- A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)
日本大学: 関与なし（対象大学）
- A quasipolynomial (2 + <i>ε</i> )-approximation for planar sparsest cut
日本大学: 関与なし（対象大学）
- A theory of universal learning
日本大学: 関与なし（対象大学）
- Adversarial laws of large numbers and optimal regret in online classification
日本大学: 関与なし（対象大学）
- Algorithmic foundations for the diffraction limit
日本大学: 関与なし（対象大学）
- Almost optimal super-constant-pass streaming lower bounds for reachability
日本大学: 関与なし（対象大学）
- An improved derandomization of the switching lemma
日本大学: 関与なし（対象大学）
- An optimal separation of randomized and Quantum query complexity
日本大学: 関与なし（対象大学）
- Approximate Gomory–Hu tree is faster than <i>n</i> – 1 max-flows
日本大学: 関与なし（対象大学）
- Approximating Nash social welfare under rado valuations
日本大学: 関与なし（対象大学）
- Automating algebraic proof systems is NP-hard
日本大学: 関与なし（対象大学）
- Average-case hardness of NP from exponential worst-case hardness assumptions
日本大学: 関与なし（対象大学）
- Bipartite perfect matching as a real polynomial
日本大学: 関与なし（対象大学）
- Boosting simple learners
日本大学: 関与なし（対象大学）
- Breaking the quadratic barrier for matroid intersection
日本大学: 関与なし（対象大学）
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
日本大学: 関与なし（対象大学）
- Capacity lower bounds via productization
日本大学: 関与なし（対象大学）
- Chasing convex bodies with linear competitive ratio (invited paper)
日本大学: 関与なし（対象大学）
- Clan embeddings into trees, and low treewidth graphs
日本大学: 関与なし（対象大学）
- Climbing algorithms (invited talk)
日本大学: 関与なし（対象大学）
- Combinatorial Bernoulli factories: matchings, flows, and other polytopes
日本大学: 関与なし（対象大学）
- Computational thinking in programming language and compiler design (keynote)
日本大学: 関与なし（対象大学）
- Constant approximating k-clique is w[1]-hard
日本大学: 関与なし（対象大学）
- Contextual search in the presence of irrational agents
日本大学: 関与なし（対象大学）
- Continuous LWE
日本大学: 関与なし（対象大学）
- Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
日本大学: 関与なし（対象大学）
- Decoding multivariate multiplicity codes on product sets
日本大学: 関与なし（対象大学）
- Decremental all-pairs shortest paths in deterministic near-linear time
日本大学: 関与なし（対象大学）
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
日本大学: 関与なし（対象大学）
- Deterministic mincut in almost-linear time
日本大学: 関与なし（対象大学）
- Discrepancy minimization via a self-balancing walk
日本大学: 関与なし（対象大学）
- Distributed weighted min-cut in nearly-optimal time
日本大学: 関与なし（対象大学）
- Dynamic planar point location in optimal time
日本大学: 関与なし（対象大学）
- Efficient and near-optimal algorithms for sampling connected subgraphs
日本大学: 関与なし（対象大学）
- Efficient list-decoding with constant alphabet and list sizes
日本大学: 関与なし（対象大学）
- Efficient randomized DCAS
日本大学: 関与なし（対象大学）
- Efficient randomized distributed coloring in CONGEST
日本大学: 関与なし（対象大学）
- Efficient two-sided markets with limited information
日本大学: 関与なし（対象大学）
- Efficiently learning halfspaces with Tsybakov noise
日本大学: 関与なし（対象大学）
- Eliminating intermediate measurements in space-bounded Quantum computation
日本大学: 関与なし（対象大学）
- Entropy decay in the Swendsen–Wang dynamics on ℤ <sup> <i>d</i> </sup>
日本大学: 関与なし（対象大学）
- Expander random walks: a Fourier-analytic approach
日本大学: 関与なし（対象大学）
- Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity
日本大学: 関与なし（対象大学）
- Exponential communication separations between notions of selfishness
日本大学: 関与なし（対象大学）
- Fiat–Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)
日本大学: 関与なし（対象大学）
- Fiber bundle codes: breaking the <i>n</i> <sup>1/2</sup> polylog( <i>n</i> ) barrier for Quantum LDPC codes
日本大学: 関与なし（対象大学）
- Finding large induced sparse subgraphs in <i> c <sub>>t</sub> </i> -free graphs in quasipolynomial time
日本大学: 関与なし（対象大学）
- Flow time scheduling with uncertain processing time
日本大学: 関与なし（対象大学）
- Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
日本大学: 関与なし（対象大学）
- Frozen 1-RSB structure of the symmetric Ising perceptron
日本大学: 関与なし（対象大学）
- Fully dynamic approximation of LIS in polylogarithmic time
日本大学: 関与なし（対象大学）
- Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
日本大学: 関与なし（対象大学）
- Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization
日本大学: 関与なし（対象大学）
- Hardness of learning DNFs using halfspaces
日本大学: 関与なし（対象大学）
- Hop-constrained oblivious routing
日本大学: 関与なし（対象大学）
- How asymmetry helps buffer management: achieving optimal tail size in cup games
日本大学: 関与なし（対象大学）
- How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design
日本大学: 関与なし（対象大学）
- Improved Quantum data analysis
日本大学: 関与なし（対象大学）
- Improved dynamic algorithms for longest increasing subsequence
日本大学: 関与なし（対象大学）
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
日本大学: 関与なし（対象大学）
- Indistinguishability obfuscation from circular security
日本大学: 関与なし（対象大学）
- Indistinguishability obfuscation from well-founded assumptions
日本大学: 関与なし（対象大学）
- Information theoretic limits of cardinality estimation: Fisher meets Shannon
日本大学: 関与なし（対象大学）
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
日本大学: 関与なし（対象大学）
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
日本大学: 関与なし（対象大学）
- Kronecker products, low-depth circuits, and matrix rigidity
日本大学: 関与なし（対象大学）
- Learnability can be independent of set theory (invited paper)
日本大学: 関与なし（対象大学）
- Learning Ising models from one or multiple samples
日本大学: 関与なし（対象大学）
- Linear bandits with limited adaptivity and learning distributional optimal design
日本大学: 関与なし（対象大学）
- Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper)
日本大学: 関与なし（対象大学）
- Load balancing with dynamic set of balls and bins
日本大学: 関与なし（対象大学）
- Local concentration inequalities and Tomaszewski’s conjecture
日本大学: 関与なし（対象大学）
- Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
日本大学: 関与なし（対象大学）
- Log-concave polynomials in theory and applications (tutorial)
日本大学: 関与なし（対象大学）
- Log-rank and lifting for AND-functions
日本大学: 関与なし（対象大学）
- Lower bounds for monotone arithmetic circuits via communication complexity
日本大学: 関与なし（対象大学）
- Minimum cost flows, MDPs, and ℓ <sub>1</sub> -regression in nearly linear time for dense instances
日本大学: 関与なし（対象大学）
- Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
日本大学: 関与なし（対象大学）
- Near-linear time decoding of Ta-Shma’s codes via splittable regularity
日本大学: 関与なし（対象大学）
- Near-optimal learning of tree-structured distributions by Chow-Liu
日本大学: 関与なし（対象大学）
- Neural tangent kernel: convergence and generalization in neural networks (invited paper)
日本大学: 関与なし（対象大学）
- New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√ <i>n</i> log <sup> <i>k</i> </sup> <i>n</i> ) distance
日本大学: 関与なし（対象大学）
- New separations results for external information
日本大学: 関与なし（対象大学）
- On codes decoding a constant fraction of errors on the BSC
日本大学: 関与なし（対象大学）
- Online stochastic matching, poisson arrivals, and the natural linear program
日本大学: 関与なし（対象大学）
- Optimal error resilience of adaptive message exchange
日本大学: 関与なし（対象大学）
- Optimal inapproximability of satisfiable k-LIN over non-abelian groups
日本大学: 関与なし（対象大学）
- Optimal labelling schemes for adjacency, comparability, and reachability
日本大学: 関与なし（対象大学）