yusuke1997/dblp-id-title huggingface dataset:
The price of anarchy is independent of the network topology
Local Borsuk-Ulam, Stability, and Replicability
Random sampling and approximation of MAX-CSP problems
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Meldable heaps and boolean union-find
Contraction decomposition in h-minor-free graphs and algorithmic applications
Almost optimal distance oracles for planar graphs
Garbled RAM From One-Way Functions
On the randomness complexity of efficient sampling
Compact Distributed Data Structures for Adaptive Routing (Extended Abstract)
Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report
On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse
Vizing's Theorem in Near-Linear Time
On the complexity of communication complexity
Every property of hyperfinite graphs is testable
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm
Contention in shared memory algorithms
On the Parallel Evaluation of Multivariate Polynomials
The complexity of non-monotone markets
Commodity-Based Cryptography (Extended Abstract)
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
The optimal error resilience of interactive communication over binary channels
On a generalization of iterated and randomized rounding
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Universal One-Way Hash Functions and their Cryptographic Applications
From affine to two-source extractors via approximate duality
Interactive information complexity
Detecting Low-Degree Truncation
Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract)
Twin-width IV: ordered graphs and matrices
Scaling and Related Techniques for Geometry Problems
New upper and lower bounds for randomized and quantum local search
The asymptotic k-SAT threshold
STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022
Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem
Prior-free auctions with ordered bidders
Parallel algorithms for geometric graph problems
Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract)
The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
Two Probabilistic Results on Rectilinear Steiner Trees
Distributed Quantum inner product estimation
Watch and learn: optimizing from revealed preferences feedback
From partial consistency to global broadcast
Average-case completeness of a word problem for groups
The Complexity of Facets (and Some Facets of Complexity)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
The shortest even cycle problem is tractable
Complexity of Implementations on the Level of Algebraic Specifications
When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract)
Area-Time Complexity for VLSI
Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract)
Location of a Point in a Planar Subdivision and its Applications
Odd cycle packing
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
Divide-and-Conquer in Multidimensional Space
Approximation Schemes for Minimum Latency Problems
Random projection trees and low dimensional manifolds
The Computational Complexity of Universal Hashing
Dual Integer Linear Programs and the Relationship between their Optima
The Cost of Consistency: Submodular Maximization with Constant Recourse
Bare quantum simultaneity versus classical interactivity in communication complexity
A cost function for similarity-based hierarchical clustering
Improved pseudorandomness for unordered branching programs through local monotonicity
A new framework for matrix discrepancy: partial coloring bounds via mirror descent
Conditions on input vectors for consensus solvability in asynchronous distributed systems
Alphabet Independent Two Dimensional Matching
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Are lock-free concurrent algorithms practically wait-free?
Unbounded lower bound for k-server against weak adversaries
Approximate counting by dynamic programming
Lower bounds for linear degeneracy testing
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes
A simple constructive computability theorem for wait-free computation
Computationally Private Information Retrieval (Extended Abstract)
Optimal Simulations by Butterfly Networks (Preliminary Version)
Quasipolynomial-time canonical form for steiner designs
On Recycling the Randomness of States in Space Bounded Computation
Hardness results for approximate hypergraph coloring
Approximating Maximum Matching Requires Almost Quadratic Time
Low-degree tests at large distances
Extractors for sumset sources
A Probabilistic Analysis of Multidimensional Bin Packing Problems
Exact Sampling and Approximate Counting Techniques
The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract)
Edge transitive ramanujan graphs and symmetric LDPC good codes
Uniform approximations for Randomized Hadamard Transforms with applications
Learning nonsingular phylogenies and hidden Markov models
On the decidability of accessibility problems (extended abstract)
Network design for vertex connectivity
Non-signaling proofs with o(√ log n) provers are in PSPACE
Denotational Semantics of Concurrency
Colouring graphs when the number of colours is nearly the maximum degree
When Won't Membership Queries Help? (Extended Abstract)
On the approximability of the traveling salesman problem (extended abstract)
Deterministic Restrictions in Circuit Complexity
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP
Efficient learning of typical finite automata from random walks
Reducibility among equilibrium problems
Probabilistic Computation and Linear Time
Mechanisms for (mis)allocating scientific credit
Maintaining exact distances under multiple edge failures
Homomorphic fingerprints under misalignments: sketching edit and shift distances
A (slightly) improved approximation algorithm for metric TSP
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
Exact algorithms for solving stochastic games: extended abstract
A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions
An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem
Statistical Inference of a Ranked Community in a Directed Graph
The omega-Sequence Equivalence Problem for DOL Systems Is Decidable
Predecessor Machines and Regressing Functions
Planted Clique Conjectures Are Equivalent
When is memorization of irrelevant training data necessary for high-accuracy learning?
Simple mechanisms for subadditive buyers via duality
Buffer overflow management in QoS switches
Edge-disjoint paths in Planar graphs with constant congestion
Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros
Quantum Lovász local lemma: Shearer's bound is tight
Flow Graph Reducibility
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem
Randomly coloring graphs of girth at least five
Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract)
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Cryptography with constant computational overhead
Randomized k-server on hierarchical binary trees
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
More deterministic simulation in logspace
Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
Subquadratic submodular function minimization
Computability and Completeness in Logics of Programs (Preliminary Report)
Computing the betti numbers of arrangements
Bounds on the Time for Parallel RAM's to Compute Simple Functions
The intrinsic dimensionality of graphs
Degree-Languages, Polynomial Time Recognition, and the LBA Problem
Revelation gap for pricing from samples
Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
Exploring Unknown Environments
Deterministic graph coloring in the streaming model
Finding the Depth of a Flow Graph
Testing Closeness of Multivariate Distributions via Ramsey Theory
Near-linear time insertion-deletion codes and (1+ ε )-approximating edit distance via indexing
Approximating the Throughput of Multiple Machines Under Real-Time Scheduling
A New Look at Fault Tolerant Network Routing
Auction algorithms for market equilibrium
The Analysis of an Improved Hashing Technique
Learnability beyond AC0
Kronecker products, low-depth circuits, and matrix rigidity
A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract)
Distinct distances in three and higher dimensions
Catalytic approaches to the tree evaluation problem
Searching in the Presence of Linearly Bounded Errors (Extended Abstract)
The Approximability of NP-hard Problems
Towards polynomial lower bounds for dynamic problems
Byzantine agreement in the full-information model in O(log n) rounds
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions
Sample-optimal tomography of quantum states
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Parallel Discrete Sampling via Continuous Walks
CSP gaps and reductions in the lasserre hierarchy
A primal-dual approximation algorithm for generalized Steiner network problems
Streaming Euclidean MST to a Constant Factor
Are bitvectors optimal?
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits
Robust Logics
A lower bound for parallel submodular minimization
Sublinear geometric algorithms
On the Computation Time of Certain Classes of Boolean Functions
On Maintaining Dynamic Information in a Concurrent Environment (Preliminary Version)
Decomposing a Polygon into its Convex Parts
Classical Commitments to Quantum States
Unbounded Fan-in Circuits and Associative Functions
Polynomial-time approximation scheme for data broadcast
Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices
Lower Bounds on the Size of Sweeping Automata
The Complexity of Theorem-Proving Procedures
More algorithms for all-pairs shortest paths in weighted graphs
On Approximating a Vertex Cover for Planar Graphs
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
How to Exchange (Secret) Keys (Extended Abstract)
A General Approach to d-Dimensional Geometric Queries (Extended Abstract)
The orbit problem in higher dimensions
Equitable cost allocations via primal-dual-type algorithms
Good Quantum LDPC Codes with Linear Time Decoders
Lower bounds for monotone arithmetic circuits via communication complexity
Issues of Correctness in Database Concurrency Control by Locking
Computational Complexity of Probabilistic Turing Machines
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
Lower bounds for intersection searching and fractional cascading in higher dimension
The Paulsen problem, continuous operator scaling, and smoothed analysis
Worst-case to average-case reductions via additive combinatorics
Uniform Definability on Finite Structures with Successor
A general framework for graph sparsification
Simple Gödel Numberings, Translations, and the P-Hierarchy
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract)
Random graphs and the parity quantifier
Fast Parallel Algorithms for Chordal Graphs (Extended Abstract)
Exponential separation of quantum communication and classical information
Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract)
A Hypercubic Sorting Network with Nearly Logarithmic Depth
Some topics in analysis of boolean functions
A constant factor approximation algorithm for a class of classification problems
Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract)
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Max cut and the smallest eigenvalue
On Broadcast Disk Paging
Generic Computation and Its Complexity
Lower Bounds for Algebraic Computation Trees (Preliminary Report)
Limitations of VCG-based mechanisms
A discrete and bounded envy-free cake cutting protocol for four agents
Rounding dynamic matchings against an adaptive adversary
Local decodability of the Burrows-Wheeler transform
Liveness Properties as Convergence in Metric Spaces
Commitments from Quantum One-Wayness
Straight-Line Program Length as a Parameter for Complexity Measures
Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face
Efficiently Learning Ising Models on Arbitrary Graphs
List decoding tensor products and interleaved codes
Recursive Properties of Abstract Complexity Classes (Preliminary Version)
Lower bounds on testing membership to a polyhedron by algebraic decision trees
Robot Navigation with Range Queries
On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
Sampling algorithms: lower bounds and applications
Optimal approximations of the frequency moments of data streams
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication
Data Type Specification: Parameterization and the Power of Specification Techniques
Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester
Subsampling Suffices for Adaptive Data Analysis
Positive Bias Makes Tensor-Network Contraction Tractable
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
NP Might Not Be As Easy As Detecting Unique Solutions
Fixed-parameter tractability of multicut parameterized by the size of the cutset
A (2 + ε )-approximation algorithm for preemptive weighted flow time on a single machine
Relational Queries Computable in Polynomial Time (Extended Abstract)
On Finding the Exact Solution of a Zero-One Knapsack Problem
Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
Do prices coordinate markets?
A new line of attack on the dichotomy conjecture
Hamiltonian complexity in the thermodynamic limit
Rigorous Time/Space Tradeoffs for Inverting Functions
General Techniques for Comparing Unrooted Evolutionary Trees
Approximating Small Sparse Cuts
Threshold Spectra for Random Graphs
Robust Recovery for Stochastic Block Models, Simplified and Generalized
Oblivious Defense in ML Models: Backdoor Removal without Detection
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography
The complexity of approximating entropy
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space
Weighted geometric set cover via quasi-uniform sampling
On coresets for k-means and k-median clustering
On Approximability of Satisfiable k-CSPs: II
Reordering buffers for general metric spaces
A universal sampling method for reconstructing signals with simple Fourier transforms
Fully-dynamic minimum spanning forest with improved worst-case update time
Almost polynomial hardness of node-disjoint paths in grids
Optimal homologous cycles, total unimodularity, and linear programming
Searching a Two Key Table Under a Single Key
Measuring independence of datasets
Planar Separators and Parallel Polygon Triangulation (Preliminary Version)
Sparse Kneser graphs are Hamiltonian
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Succinct delegation for low-space non-deterministic computation
The Wakeup Problem (Extended Abstract)
The power of simple tabulation hashing
Extractors with weak random seeds
(Gap/S)ETH hardness of SVP
Separating Concurrent Languages with Categories of Language Embeddings (Extended Abstract)
Hypergraph Isomorphism and Structural Equivalence of Boolean Functions
Graph Decomposition Is NPC-A Complete Proof of Holyer's Conjecture
Optimal Randomized Algorithms for Local Sorting and Set-Maxima
Semigroup Algorithmic Problems in Metabelian Groups
New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√ n log k n ) distance
Adaptively Secure Multi-Party Computation
An optimal lower bound on the communication complexity of gap-hamming-distance
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada
High Parallel Complexity Graphs and Memory-Hard Functions
From information to exact communication
Generalized FLP impossibility result for t-resilient asynchronous computations
Two Algorithms for Maintaining Order in a List
Asymptotic Tensor Rank Is Characterized by Polynomials
Faster Distributed Δ-Coloring via Ruling Subgraphs
How Well Can Graphs Represent Wireless Interference?
Modified log-sobolev inequalities, mixing and hypercontractivity
Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, May 4-6, 1970, Northampton, Massachusetts, USA
Randomized competitive algorithms for generalized caching
Lift-and-round to improve weighted completion time on unrelated machines
On Structuring Flowcharts (Preliminary Version)
Logconcave random graphs
Non-Gaussian component analysis using entropy methods
Incomplete nested dissection
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity
Managing Storage for Extendible Arrays
Propositional Representation of Arithmetic Proofs (Preliminary Version)
On-Line Learning of Linear Functions
The Optimal Fixedpoint of Recursive Programs
Simple strategies for large zero-sum games with applications to complexity theory
Graphs, polymorphisms and the complexity of homomorphism problems
Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
Constructing Nonresidues in Finite Fields and the Extended Riemann Hypothesis
Deterministic Sampling-A New Technique for Fast Pattern Matching
Universal semantic communication I
A sharp threshold in proof complexity
A tight RMR lower bound for randomized mutual exclusion
Adversarial Queueing Theory
Toward a general theory of quantum games
Bootstrapping results for threshold circuits "just beyond" known lower bounds
A Unifying Theory of Distance from Calibration
Efficient list-decoding with constant alphabet and list sizes
How to share a function securely
Improved and Deterministic Online Service with Deadlines or Delay
A polynomial lower bound for testing monotonicity
Locality-sensitive orderings and applications to reliable spanners
Exponential separation of communication and external information
Reed-Muller Codes for Random Erasures and Errors
Local zero knowledge
Shortest path queries in planar graphs
Quantum weak coin flipping
Minimum Spanning Ellipsoids
What do we know about the Metropolis algorithm?
Optimization, Approximation, and Complexity Classes (Extended Abstract)
Agnostic Smoothed Online Learning
The Hypergraph Removal Process
Testing juntas nearly optimally
Byzantine agreement in polynomial time with near-optimal resilience
Quantum algorithms a decade after shor
Pricing network edges for heterogeneous selfish users
An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP
Bayesian algorithmic mechanism design
Efficiently learning mixtures of two Gaussians
On Bounds on the Number of Steps to Compute Functions
Efficiently Four-Coloring Planar Graphs
New Real-Time Simulations of Multihead Tape Units
Dimension Independent and Computationally Efficient Shadow Tomography
Time-space trade-offs for predecessor search
Learning Mixtures of Gaussians in High Dimensions
Efficient noise-tolerant learning from statistical queries
Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing (Extended Abstract)
Implementing geometric complexity theory: on the separation of orbit closures via symmetries
On the Complexity of Bilinear Forms with Commutativity
Domolki's Algorithm Applied to Generalized Overlap Resolvable Grammars
Planning Constrained Motion
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Algorithmic Contract Design (Keynote)
Towards the locality of Vizing's theorem
Approximate counting, the Lovasz local lemma, and inference in graphical models
Preserving Statistical Validity in Adaptive Data Analysis
Fine-grained reductions from approximate counting to decision
Contention resolution with log-logstar channel accesses
Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows
Near-Optimal Dimension Reduction for Facility Location
Server scheduling in the L p norm: a rising tide lifts all boat
On obfuscating point functions
Dynamic Maxflow via Dynamic Interior Point Methods
The complexity of verification
The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract)
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes
A New Berry-Esseen Theorem for Expander Walks
Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers
Watermarking cryptographic capabilities
Fault-tolerant spanners for general graphs
Tight Bounds for Learning a Mixture of Two Gaussians
On the Equivalence of Schemes
Succinct Randomized Encodings and their Applications
Stochastic matching with few queries: (1-ε) approximation
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality
Hardness amplification within NP
Affine dispersers from subspace polynomials
Non-commutative circuits and the sum-of-squares problem
Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Low-temperature Ising dynamics with random initializations
Deciding Branching Time Logic
The complexity of computing a Nash equilibrium
Computations with a Restricted Number of Nondeterministic Steps (Extended Abstract)
Counting Small Induced Subgraphs with Edge-Monotone Properties
Basis collapse for holographic algorithms over all domain sizes
On the complexity of local distributed graph problems
On the Optimal Fixed-Price Mechanism in Bilateral Trade
Noise-Tolerant Learning Near the Information-Theoretic Bound
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication
Clique-width minimization is NP-hard
Approximate sparse recovery: optimizing time and measurements
Faster k -SAT algorithms using biased-PPSZ
Management of multi-queue switches in QoS networks
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Optimal time and space leader election in population protocols
A Nearly Quadratic-Time FPTAS for Knapsack
Lifting nullstellensatz to monotone span programs over any field
On transformation of interactive proofs that preserve the prover's complexity
Security of quantum protocols against coherent measurements
Two Nonlinear Lower Bounds
Nonlinear dimension reduction via outer Bi-Lipschitz extensions
Degree-constrained network flows
A reverse Minkowski theorem
Improving christofides' algorithm for the s-t path TSP
Treewidth Inapproximability and Tight ETH Lower Bound
Fast On-Line Integer Multiplication
Quantum garbled circuits
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games