yusuke1997/dblp-id-title huggingface dataset:
Horn Clauses and Database Dependencies (Extended Abstract)
Lower bound for succinct range minimum query
Efficient decoding of random errors for quantum expander codes
Crawling on web graphs
Lower bounds on the efficiency of encryption and digital signature schemes
Edge-Deletion and Edge-Contraction Problems
Coherent Functions and Program Checkers (Extended Abstract)
Optimal Eigenvalue Approximation via Sketching
Constant factor approximations to edit distance on far input pairs in nearly linear time
Metric Distortion of Small-Group Deliberation
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time
A simple polynomial-time rescaling algorithm for solving linear programs
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Algorithmic Mechanism Design (Extended Abstract)
Combinatorial walrasian equilibrium
The detectability lemma and quantum gap amplification
Almost-linear ε -emulators for planar graphs
Parallel repetition of entangled games
On Some Families of Languages Related to the Dyck Language
Algorithms for Edge Coloring Bipartite Graphs
Lossy trapdoor functions and their applications
The condition number of a randomly perturbed matrix
Improved Stabilizer Estimation via Bell Difference Sampling
The Power of Randomness for Communication Complexity (Preliminary Version)
Bounded-concurrent secure multi-party computation with a dishonest majority
The Complexity of Cutting Convex Polytopes
Covert two-party computation
Tree Transductions and Families of Tree Languges
Subspace embeddings for the L 1 -norm with applications
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
Online Minimization of Transition Systems (Extended Abstract)
Detecting and counting small patterns in planar graphs in subexponential parameterized time
Highly Parallelizable Problems (Extended Abstract)
An O(\mathop lg n) Expected Rounds Randomized Byzantine Generals Protocol
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits
An Internal Semantics for Modal Logic: Preliminary Report
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions
Communication with Secrecy Constraints
Hard-Potato routing
Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract)
Subspace evasive sets
The Directed Grid Theorem
Fully polynomial Byzantine agreement in t+1 rounds
Approximation of k -Set Cover by Semi-Local Optimization
Bernoulli factories and black-box reductions in mechanism design
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL
Discovering the roots: uniform closure results for algebraic classes under factoring
Reversal Complexity of Counter Machines
Elusive functions and lower bounds for arithmetic circuits
Exact learning of DNF formulas using DNF hypotheses
Spectral methods from tensor networks
Approximate counting of inversions in a data stream
Approximately efficient bilateral trade
An Optimal Online Algorithm for Metrical Task Systems
On the parameterized complexity of approximating dominating set
How to Generate Random Integers with Known Factorization
Quantum and classical query complexities of local search are polynomially related
k-forrelation optimally separates Quantum and classical query complexity
A new approach to auctions and resilient mechanism design
On Translating a Set of Rectangles
Faster Isomorphism Testing of Strongly Regular Graphs
The cell probe complexity of dynamic range counting
Property Testing in Bounded Degree Graphs
The complexity of agreement
Satisfiability of Word Equations with Constants is in NEXPTIME
More on the complexity of negation-limited circuits
Sublinear Time Algorithms for Metric Space Problems
The round complexity of two-party random selection
On the Time Complexity of Broadcast Communication Schemes (Preliminary Version)
How Random CSPs Fool Hierarchies: II
Generating Random Spanning Trees More Quickly than the Cover Time
Net and prune: a linear time algorithm for euclidean distance problems
Budget constrained auctions with heterogeneous items
Linear programming without the matrix
A weighted linear matroid parity algorithm
Non-malleable codes and extractors for small-depth circuits, and affine functions
The chow parameters problem
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
Deterministic extractors for small-space sources
A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms
Critical Path Scheduling of Task Systems with Resource and Processor Constraints (Extended Abstract)
On the concrete efficiency of probabilistically-checkable proofs
Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
New approximation guarantee for chromatic number
Retraction: A New Approach to Motion-Planning (Extended Abstract)
Explicit construction of a small epsilon-net for linear threshold functions
Strictly non-blocking WDM cross-connects for heterogeneous networks
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
Efficient testing of groups
Optimal Simulations between Mesh-Connected Arrays of Processors (Preliminary Version)
Inapproximability of Nash Equilibrium
Leakage-Resilient Extractors against Number-on-Forehead Protocols
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA
Hypercontractivity, sum-of-squares proofs, and their applications
Approximation algorithms for constrained for constrained node weighted steiner tree problems
Completeness in two-party secure computation: a computational view
Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications)
The power of two choices in graphical allocation
Interactive compression for product distributions
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
Climbing algorithms (invited talk)
Optimal Parallel Algorithms for String Matching
Complete Register Allocation Problems
The maximum multiflow problems with bounded fractionality
The Discrete Log is Very Discreet
Optimal Online Discrepancy Minimization
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
New Bounds for Parallel Prefix Circuits
Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks
Constant girth approximation for directed graphs in subquadratic time
Quantum-Computable One-Way Functions without One-Way Functions
Extractors: optimal up to constant factors
Hardness of the undirected congestion minimization problem
Expanders that beat the eigenvalue bound: explicit construction and applications
The Computer in the Sky (Keynote)
Not All Keys Can Be Hashed in Constant Time (Preliminary Version)
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
A unified framework for approximating and clustering data
On the n^log n Isomorphism Technique: A Preliminary Report
Message passing algorithms and improved LP decoding
Bandwidth Constrained NP-Complete Problems
Sampling Lattice Points
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
Hardness of 4-Colouring k-Colourable Graphs
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Testing Flow Graph Reducibility
Tight conditional lower bounds for approximating diameter in directed graphs
A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract)
Stackelberg scheduling strategies
Deterministic (1+ ε )-approximate maximum matching with poly(1/ ε ) passes in the semi-streaming model and beyond
From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking
Scalable expanders: exploiting hierarchical random wiring
Playing games with approximation algorithms
Pointer Jumping Requires Concurrent Read
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Exponential separation of quantum and classical one-way communication complexity
How to Sign Given Any Trapdoor Function (Extended Abstract)
Computing Moment Polytopes of Tensors, with Applications in Algebraic Complexity and Quantum Information
Achieving optimal backlog in multi-processor cup games
Hardness of the undirected edge-disjoint paths problem
On the Number of Additions to Compute Specific Polynomials (Preliminary Version)
Efficient profile maximum likelihood for universal symmetric property estimation
Oblivious routing in directed graphs with random demands
Lower-stretch spanning trees
On the Complexity of Unsatisfiability Proofs for Random k -CNF Formulas
Optimal oblivious reconfigurable networks
Loss-less condensers, unbalanced expanders, and extractors
Constructing small sample spaces satisfying given constraints
Fast hashing with strong concentration bounds
Associative Retrieval Trie Hash-Coding
One-Way Functions and Zero Knowledge
On proximity oblivious testing
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
An Approximation Algorithm for Manhattan Routing (Extended Abstract)
Quantitative solution of omega-regular games
Lower bounds for dynamic connectivity
Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
Universal Schemes for Parallel Communication
Decidability of Reachability in Vector Addition Systems (Preliminary Version)
An improved derandomization of the switching lemma
Integrality gaps for sparsest cut and minimum linear arrangement problems
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Dynamic matching in school choice: efficient seat reassignment after late cancellations (invited talk)
Checking Polynomial Identities over any Field: Towards a Derandomization?
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Local embeddings of metric spaces
Formulas vs. circuits for small distance connectivity
The ghost in the radiation: robust encodings of the black hole interior (invited paper)
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies
Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Deciding parity games in quasipolynomial time
A Zero-Knowledge PCP Theorem
Faster approximate multicommodity flow using quadratically coupled flows
Optimal Tree Layout (Preliminary Version)
Shortest paths on polyhedral surfaces and terrains
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Optimality and domination in repeated games with bounded players
Finding paths and cycles of superpolylogarithmic length
Synchronization strings: codes for insertions and deletions approaching the Singleton bound
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Every monotone graph property is testable
Explicit near-Ramanujan graphs of every degree
The online k-taxi problem
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond
Fast convergence of learning in games (invited talk)
BQP and the polynomial hierarchy
A quasipolynomial-time algorithm for the quantum separability problem
Pseudodeterminism: promises and lowerbounds
On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem
A Parallel Algorithm for the Maximal Path Problem
Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field
New Algorithms for an Ancient Scheduling Problem
Reconstructing curves in three (and higher) dimensional space from noisy data
Computing the first Betti number and the connected components of semi-algebraic sets
A conjecture about polynomial time computable lattice-lattice functions
Lower bounds for external memory integer sorting via network coding
Concurrent zero-knowledge with timing, revisited
Linear FPT reductions and computational lower bounds
Better streaming algorithms for clustering problems
Space-efficient approximate Voronoi diagrams
Verifying the unseen: interactive proofs for label-invariant distribution properties
A Probabilistic Algorithm for the Post Office Problem
Almost settling the hardness of noncommutative determinant
Derandomizing homomorphism testing in general groups
On the Completeness of a Generalized Matching Problem
Maze Recognizing Automata (Extended Abstract)
Explicit dispersers with polylog degree
Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025
Some Connections between Nonuniform and Uniform Complexity Classes
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
The myth of the folk theorem
Learning low-degree functions from a logarithmic number of random queries
On Time Hierarchies
Instance optimal learning of discrete distributions
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Randomized Rounding for the Largest Simplex Problem
On the Second Eigenvalue in Random Regular Graphs
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
The Complexity of Multiway Cuts (Extended Abstract)
Constant-factor approximation for ordered k-median
A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines
Classical deterministic complexity of Edmonds' Problem and quantum entanglement
Optimal phylogenetic reconstruction
Size-depth trade-offs for threshold circuits
Canonical Labeling of Graphs
Low-Step Multi-commodity Flow Emulators
Uniform sampling through the Lovasz local lemma
A Practical Decision Method for Propositional Dynamic Logic: Preliminary Report
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
The Subgraph Homeomorphism Problem
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
Optimal Size Integer Division Circuits
The matching polytope has exponential extension complexity
Is Linear Hashing Good?
Agnostically learning decision trees
Competitive recommendation systems
Concurrent Dynamic Logic (Extended Abstract)
Quadratic speedup for finding marked vertices by quantum walks
Purely Functional Representations of Catenable Sorted Lists
Characterizing and Testing Principal Minor Equivalence of Matrices
Thermodynamics of computation and information distance
The price of anarchy of finite congestion games
Estimating true evolutionary distances between genomes
Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection
New classes of distributed time complexity
The zero-one principle for switching networks
Recycling Queries in PCPs and in Linearity Tests (Extended Abstract)
PP Is Closed Under Intersection (Extended Abstract)
Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs
Efficient Algorithms for Inverting Evolution
Quantum Free Games
Bounded-concurrent secure two-party computation without setup assumptions
A nearly optimal time-space lower bound for directed st -connectivity on the NNJAG model
Online load balancing and network flow
Efficiently decoding Reed-Muller codes from random errors
Distributed computability in Byzantine asynchronous systems
Lower bounds in communication complexity based on factorization norms
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set
Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada
Can every randomized algorithm be derandomized?
Parallel algorithms for algebraic problems
Switching Functions Whose Monotone Complexity Is Nearly Quadratic
Complexity Problems in Real Time Computation
Geometric Complexity
Construction of Extractors Using Pseudo-Random Generators (Extended Abstract)
Optimal CUR matrix decompositions
Provably Learning a Multi-head Attention Layer
Complexity of Finitely Presented Algebras
Approximation algorithms for minimum norm and ordered optimization problems
Using mixture models for collaborative filtering
On the Power of White Pebbles (Extended Abstract)
A Decision Procedure for Generalized Sequential Mapability-onto of Regular Sets
Algebraic attacks against random local functions and their countermeasures
Random Sampling of Large Planar Maps and Convex Polyhedra
Now You May Compose Temporal Logic Specifications
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996
Context-Free Error Analysis by Evaluation of Algebraic Power Series
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA
Prior-independent mechanisms for scheduling
A Tolerant Independent Set Tester
Relativized Polynominal Time Hierarchies Having Exactly K Levels
(Fractional) online stochastic matching via fine-grained offline statistics
External Memory Fully Persistent Search Trees
Some Properties of Precedence Languages
Planar diameter via metric compression
A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
A full derandomization of schöning's k-SAT algorithm
Limits to list decodability of linear codes
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
An O(log N) Deterministic Packet Routing Scheme (Preliminary Version)
Characterizing pseudoentropy and simplifying pseudorandom generator constructions
The complexity of temporal constraint satisfaction problems
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors
On the Complexity of Local Search (Extended Abstract)
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract)
Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems
Type Two Computational Complexity
Competitive generalized auctions
Lower bounds for union-split-find related problems on random access machines
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations
Quantum algorithms using the curvelet transform
A (de)constructive approach to program checking
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)
Approximating Geometrical Graphs via "Spanners" and "Banyans"
Decodability of group homomorphisms beyond the johnson bound
Non-Blocking Networks (Preliminary Version)
On complexity as bounded rationality (extended abstract)
The average sensitivity of an intersection of half spaces
On Feasible Numbers (Preliminary Version)
An Exponential Lower Bound for Depth 3 Arithmetic Circuits
Distributed edge connectivity in sublinear time
Analyzing network coding gossip made easy
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Algorithmic foundations for the diffraction limit
Constant factor approximation of vertex-cuts in planar graphs
Terminal backup, 3D matching, and covering cubic graphs
Storing and Searching a Multikey Table (Extended Abstract)
On Notions of Information Transfer in VLSI Circuits
Characterizing non-deterministic circuit size
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA
Verifying candidate matches in sparse and wildcard matching
Differential privacy and robust statistics
How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design
Towards tight approximation bounds for graph diameter and eccentricities
Randomized polynomial time identity testing for noncommutative circuits
Prioritized Metric Structures and Embedding
List-decodable robust mean estimation and learning mixtures of spherical gaussians
Improved smoothed analysis of multiobjective optimization
Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract)
Alpha-shapes and flow shapes are homotopy equivalent
The complexity of gradient descent: CLS = PPAD ∩ PLS
Flows in almost linear time via adaptive preconditioning
A new family of Cayley expanders (?)
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
Learning juntas
Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and differential privacy
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023
How Random CSPs Fool Hierarchies
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
The sample complexity of revenue maximization
Optimizing strongly interacting fermionic Hamiltonians
QCSP monsters and the demise of the chen conjecture
Fiat-Shamir: from practice to theory
Learning from untrusted data
A constant-factor approximation for the k -MST problem in the plane
Detecting high log-densities: an O ( n 1/4 ) approximation for densest k -subgraph
Sample-Optimal Private Regression in Polynomial Time
Single-Sample and Robust Online Resource Allocation
Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract)
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract)
Properties of Acyclic Database Schemes
Clan embeddings into trees, and low treewidth graphs
Separating multilinear branching programs and formulas
Towards tight bounds for spectral sparsification of hypergraphs
A fixed-parameter algorithm for the directed feedback vertex set problem
Propositional Modal Logic of Programs (Extended Abstract)
On zero-knowledge proofs (extended abstract): "from membership to decision"
A Logspace Algorithm for Tree Canonization (Extended Abstract)
The computational complexity of some julia sets
Lower bounds for cutting planes proofs with small coefficients
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract
Dynamic sampling from graphical models
Learning the Structure of Any Hamiltonian from Minimal Assumptions
On the structure of cubic and quartic polynomials
Proof of the Satisfiability Conjecture for Large k
Hamiltonian Paths in Infinite Graphs
AND testing and robust judgement aggregation
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA
Caching with time windows
Parallel Scheduling of Programs in a Restricted Model of Computation
An improved constant-time approximation algorithm for maximum matchings
A Hard-Core Predicate for all One-Way Functions
Alpha-algorithms for incremental planarity testing (preliminary version)
Competitive Algorithms for On-line Problems
(Semi)Algebraic proofs over ±1 variables
The amazing power of pairwise independence (abstract)
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams
Differential privacy under continual observation
Strong Algebras and Radical Sylvester-Gallai Configurations
Well-separated pair decomposition for the unit-disk graph metric and its applications
A theory of clock synchronization (extended abstract)
On the existence of extractable one-way functions
Constant round non-malleable protocols using one way functions
k one-way heads cannot do string-matching
A Provably Efficient Algorithm for Dynamic Storage Allocation
Knapsack with Small Items in Near-Quadratic Time
Hierarchies Based on Computational Complexity and Irregularities of Class Determining Measured Sets (Preliminary Report)