yusuke1997/dblp-id-title huggingface dataset:
Compact Grid Layouts of Multi-Level Networks
Permutation Superposition Oracles for Quantum Query Lower Bounds
A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem
Rapid Mixing at the Uniqueness Threshold
Languages Which Capture Complexity Classes (Preliminary Report)
Sum-of-squares Lower Bounds for Planted Clique
Finding Hidden Hamiltonian Cycles (Extended Abstract)
Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract)
A New Grammatical Transformation into LL(k) Form (Extended Abstract)
The approximate rank of a matrix and its algorithmic applications: approximate rank
Spectral Techniques for Expander Codes
An LLL-reduction algorithm with quasi-linear time complexity: extended abstract
Large-scale assembly of DNA strings and space-efficient construction of suffix trees
Pseudorandom generators and learning algorithms for AC
Hardness of Graph Pricing Through Generalized Max-Dicut
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Primal-dual meets local search: approximating MST's with nonuniform degree bounds
A Sublinear Bipartiteness Tester for Bunded Degree Graphs
Sparsified Cholesky and multigrid solvers for connection laplacians
Bounds for the computational power and learning complexity of analog neural nets
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Schaefer's theorem for graphs
Eisenberg-Gale markets: algorithms and structural properties
A New Polynomial-Time Algorithm for Linear Programming
The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems
Analytical approach to parallel repetition
Limits on the Power of Concurrent-Write Parallel Machines
k-server via multiscale entropic regularization
Locality based graph coloring
Zero-knowledge against quantum attacks
Indistinguishability obfuscation from well-founded assumptions
Santa Claus schedules jobs on unrelated machines
Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities
Maintaining a large matching and a small vertex cover
The Pagenumber of Genus g Graphs is O(g)
Many birds with one stone: multi-objective approximation algorithms
On the Problem of Computational Time and Complexity of Arithmetic Functions
Linear matroid intersection is in quasi-NC
On Decomposing Languages Defined by Parallel Devices
On the Stability of the Ethernet
Clique Partitions, Graph Compression, and Speeding-Up Algorithms
On earthmover distance, metric labeling, and 0-extension
Memory Checking Requires Logarithmic Overhead
The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
Randomized metarounding (extended abstract)
2-round zero knowledge and proof auditors
Approximation algorithms for budgeted learning problems
Fault-tolerant scheduling
Information-theoretically secure protocols and security under composition
How to leak on key updates
Space Bounds for a Game of Graphs
Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version)
Multiparty computation secure against continual memory leakage
Does preprocessing help in fast sequence comparisons?
Approximating the minimum bisection size (extended abstract)
Short proofs for the determinant identities
Smooth heaps and a dual view of self-adjusting data structures
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004
Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios
Tight bounds for parallel randomized load balancing: extended abstract
A Simple Parallel Algorithm for the Maximal Independent Set Problem
The Complexity of Computing KKT Solutions of Quadratic Programs
Lower Bounds for Noisy Boolean Decision Trees
Concurrent general composition of secure protocols in the timing model
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
Improved algorithms for min cut and max flow in undirected planar graphs
Quantum walks on graphs
Computational thinking in programming language and compiler design (keynote)
Fine-grained complexity for sparse graphs
A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)
Approximating the cut-norm via Grothendieck's inequality
First-Order Model Checking on Structurally Sparse Graph Classes
Embedding Graphs in an Arbitrary Surface in Linear Time
Optimal Evaluation of Pairs of Bilinear Forms
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Constant factor approximation for balanced cut in the PIE model
A parallel repetition theorem
Perfectly One-Way Probabilistic Hash Functions (Preliminary Version)
Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
The Predicate Elimination Strategy in Theorem Proving
Computing crossing numbers in quadratic time
How hard is to marry at random? (On the approximation of the permanent)
On the Lengths of Proofs in the Propositional Calculus (Preliminary Version)
Settling the sample complexity of single-parameter revenue maximization
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
Bridging between 0/1 and linear programming via random walks
Fully Dynamic Biconnectivity in Õ(log² n) Time
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
Low Level Complexity for Combinatorial Games
Fair Division via Quantile Shares
Uniform direct product theorems: simplified, optimized, and derandomized
A phase transition and a quadratic time unbiased estimator for network reliability
Self-routing superconcentrators
Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
The communication complexity of multiparty set disjointness under product distributions
Reachability in One-Dimensional Pushdown Vector Addition Systems Is Decidable
Simple Algebras Are Difficult
Local and Global Properties in Networks of Processors (Extended Abstract)
The Harmonic Online K-Server Algorithm Is Competitive
Better algorithms for unfair metrical task systems and applications
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
Time-Space Tradeoffs for some Algebraic Problems
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
Solving tall dense linear programs in nearly linear time
A Sharp Version of Talagrand's Selector Process Conjecture and an Application to Rounding Fractional Covers
Near-optimal fully dynamic densest subgraph
Graphs that Are Almost Binary Trees (Preliminary Version)
Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space
A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract)
Towards the Learnability of DNF Formulae
Minimum Star Partitions of Simple Polygons in Polynomial Time
How to delegate computations publicly
On the complexity of equilibria
On metric ramsey-type phenomena
Covering Approximate Shortest Paths with DAGs
Toward Mechanical Verification of Properties of Roundoff Error Propagation
A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes
How to compress interactive communication
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
Min-Wise Independent Permutations (Extended Abstract)
Factoring Numbers Using Singular Integers
The price of anarchy in large games
A size-free CLT for poisson multinomials and its applications
Supermodular Approximation of Norms and Applications
Chasing convex bodies with linear competitive ratio (invited paper)
An algorithm for the graph crossing number problem
Turnstile streaming algorithms might as well be linear sketches
An Algorithm for Finding Hamilton Cycles in a Random Graph
Computing Algebraic Formulas Using a Constant Number of Registers
Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
Batch codes and their applications
Approximation Algorithms for Facility Location Problems (Extended Abstract)
Symmetry and Complexity
The program-size complexity of self-assembled squares (extended abstract)
Some Complexity Results for the Traveling Salesman Problem
A General Result on Infinite Trees and Its Applications (Preliminary Report)
Approximation algorithms for semi-random partitioning problems
Extractors for Images of Varieties
Perfect Cryptographic Security from Partially Independent Channels
Additive guarantees for degree bounded directed network design
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Maximization Problems on Graphs with Edge Weights Chosen from a Normal Distribution (Extended Abstract)
Unconstrained submodular maximization with constant adaptive complexity
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS
Constant time factors do matter
Computational thresholds for the fixed-magnetization Ising model
0-1 Knapsack in Nearly Quadratic Time
Pseudorandom walks on regular digraphs and the RL vs. L problem
Learning a circuit by injecting values
Probabilistic Analysis of Bandwidth Minimization Algorithms
Collective asynchronous reading with polylogarithmic worst-case overhead
Approximate k-flat Nearest Neighbor Search
The one-way communication complexity of submodular maximization with applications to streaming and robustness
Learning the Closest Product State
Spectral norm of random matrices
Optimally resilient codes for list-decoding from insertions and deletions
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Optimal Embedding Dimension for Sparse Subspace Embeddings
SL <= L 4/3
Spectral methods for matrices and tensors
Faster space-efficient algorithms for subset sum and k-sum
Solving fractional packing problems in O ast (1/?) iterations
Information Theoretic Implications for Pairing Heaps
Deniable encryption in a Quantum world
A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields (Preliminary Version)
A tighter welfare guarantee for first-price auctions
A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata
On the Necessity of Occam Algorithms
The complexity of pure Nash equilibria
Quantum complexity theory
A minimal model for secure computation (extended abstract)
A tight lower bound for searching a sorted array
Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-LIN over Expanders
Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev
Sampling random spanning trees faster than matrix multiplication
Matrix searching with the shortest path metric
Computing a Fixed Point of Contraction Maps in Polynomial Queries
Tree Pattern Matching and Subset Matching in Randomized O(n log 3 m) Time
Touring a sequence of polygons
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report
Lower Bounds for Randomized k-Server and Motion Planning Algorithms
A robust model for finding optimal evolutionary trees
Quantum mechanical algorithms for the nonabelian hidden subgroup problem
Approximation schemes for preemptive weighted flow time
Polynomial-Time Tolerant Testing Stabilizer States
Greed is good: approximating independent sets in sparse and bounded-degree graphs
A linear time algorithm for finding tree-decompositions of small treewidth
A Complete Axiomatization for a Large Class of Dependencies in Relational Databases
Local search heuristic for k-median and facility location problems
Lower bounds for sorting networks
Fiber bundle codes: breaking the n 1/2 polylog( n ) barrier for Quantum LDPC codes
Multi-linear formulas for permanent and determinant are of super-polynomial size
Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria
Composable and efficient mechanisms
A super-polynomial lower bound for regular arithmetic formulas
Polynomial-time perfect matchings in dense hypergraphs
Efficient Parallel Solution of Linear Systems
Pushing Disks Together - The Continuous-Motion Case
Communication complexity of estimating correlations
Strong Signature Schemes
Edge partition of planar sraphs into two outerplanar graphs
Twice-ramanujan sparsifiers
A subset spanner for Planar graphs, : with application to subset TSP
New results on monotone dualization and generating hypergraph transversals
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes
Towards a better understanding of randomized greedy matching
Uniform hashing in constant time and linear space
Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
The Power of Two-Sided Recruitment in Two-Sided Markets
Randomness efficient identity testing of multivariate polynomials
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
A complete dichotomy rises from the capture of vanishing signatures: extended abstract
The Glauber dynamics on colourings of a graph with high girth and maximum degree
Cryptographic defense against traffic analysis
Nonmonotonic Phenomena in Packet Routing
Strong direct product theorems for quantum communication and query complexity
On the need for large quantum depth
The Orbit Problem is Decidable
On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)
Further Applications of Random Sampling to Computational Geometry
Vector Execution of Flow Graphs (Extended Abstract)
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
An Observation on Time-Storage Trade Off
Almost Optimal Dispersers
Separations and equivalences between turnstile streaming and linear sketching
Covering Rectilinear Polygons with Axis-Parallel Rectangles
Stronger l 2 /l 2 compressed sensing; without iterating
Exponential Lower Bounds for the Pigeonhole Principle
Randomized Complexity Lower Bounds
The complexity of searching a sorted array of strings
A Black Box Approach to the Algebraic Set Decomposition Problem
Derandomizing polynomial identity tests means proving circuit lower bounds
The Linear-Array Problem in Communication Complexity Resolved
Kneser Graphs Are Hamiltonian
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs
Rectangles Are Nonnegative Juntas
Computational geometry: a retrospective
Improved non-malleable extractors, non-malleable codes and independent source extractors
Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)
Large-treewidth graph decompositions and applications
A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper)
The Analysis of Two-Dimensional Patterns using Picture Processing Grammars
Linear Time Bounds for Median Computations
On Separating the Read-k-Times Branching Program Hierarchy
Model Stealing for Any Low-Rank Language Model
A quantitative gibbard-satterthwaite theorem without neutrality
Harmonic Decomposition in Data Sketches
Weighted Edit Distance Computation: Strings, Trees, and Dyck
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)
Perfect matchings in o( n log n ) time in regular bipartite graphs
A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Optimal principal component analysis in distributed and streaming models
Lower bounds for randomized read/write stream algorithms
Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations
Superlinear advantage for exact quantum algorithms
Approximating k-median via pseudo-approximation
Hit-and-run from a corner
Testing thresholds for high-dimensional sparse random geometric graphs
An exponential time parameterized algorithm for planar disjoint paths
Permutation Groups in NC
A Randomized Parallel Branch-and-Bound Procedure
Vertex cuts, random walks, and dimension reduction in series-parallel graphs
Online matching: haste makes waste!
Planning and Learning in Partially Observable Systems via Filter Stability
Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees
Approximation Algorithms for Combinatorial Problems
An optimal distributed (Δ+1)-coloring algorithm?
When is the evaluation of conjunctive queries tractable?
Decidability of string graphs
Almost tight bounds for eliminating depth cycles in three dimensions
Quantum Time-Space Tradeoffs for Matrix Problems
Hitting sets for multilinear read-once algebraic branching programs, in any order
Biconnectivity Approximations and Graph Carvings
Sets that Don't Help
Quantifiers and Approximation (Extended Abstract)
The (True) Complexity of Statistical Zero Knowledge
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Multi-way spectral partitioning and higher-order cheeger inequalities
Approximate Testing with Relative Error
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
New independent source extractors with exponential improvement
Neural tangent kernel: convergence and generalization in neural networks (invited paper)
Self-Organizing Sequential Search and Hilbert's Inequalities
On cryptography with auxiliary input
The two possible values of the chromatic number of a random graph
Inerpolation of Symmetric Functions and a New Type of Combinatorial Design
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)
The Karger-Stein algorithm is optimal for k-cut
Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences
Online and stochastic survivable network design
An exponential lower bound for individualization-refinement algorithms for graph isomorphism
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA
A tight time lower bound for space-optimal implementations of multi-writer snapshots
Transitive Orientation in O(n²) Time
Deterministic sorting in O(nlog log n) time and linear space
Sketching in adversarial environments
Solution of the propeller conjecture in R 3
Deadlock- and Livelock-Free Packet Switching Networks
Holiest minimum-cost paths and flows in surface graphs
The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA
Finding Small Simple Cycle Separators for 2-Connected Planar Graphs
VC dimension and distribution-free sample-based testing
Constant-Cost Communication Is Not Reducible to k-Hamming Distance
On the computability of continuous maximum entropy distributions with applications
Competitive distributed file allocation
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
Automata Theoretic Techniques for Modal Logics of Programs (Extended Abstract)
Small-bias Probability Spaces: Efficient Constructions and Applications
On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract)
Approximate Distance Oracles with Improved Bounds
Computing with a full memory: catalytic space
Modified ranks of tensors and the size of circuits
Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
Bounded Concurrent Time-Stamp Systems Are Constructible
Some Simplified NP-Complete Problems
Hardness of learning DNFs using halfspaces
Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
Separators in Two and Three Dimensions
Formalization of Properties of Recursively Defined Functions
Trees, Automata, and Games
Wait-free made fast (Extended Abstract)
Privately Evaluating Untrusted Black-Box Functions
Almost Chor-Goldreich Sources and Adversarial Random Walks
A Fast Quantum Mechanical Algorithm for Database Search
How to Reuse a "Write-Once" Memory (Preliminary Version)
Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms
Learning geometric concepts with nasty noise
Secretary Problems with Non-Uniform Arrival Order
A Faster Strongly Polynominal Minimum Cost Flow Algorithm
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5-7, 1969, Marina del Rey, CA, USA
Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
Multi-Party Protocols
A characterization of strong approximation resistance
A Unified Approach to Models of Synchronous Parallel Machines
Distributed Elections in an Archimedean Ring of Processors (Preliminary Version)
Almost all graphs with average degree 4 are 3-colorable
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Randomly supported independence and resistance
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Making Zero-Knowledge Provers Efficient
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Algorithmic Applications of Hypergraph and Partition Containers
Time bounds for mutual exclusion and related problems
Entropy, optimization and counting
Quantum algorithms for solvable groups
Reasoning about Fair Concurrent Programs
Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees (Extended Abstract)
Finding Approximate Separators and Computing Tree Width Quickly
On the complexity of trial and error
Tight Conditional Lower Bounds for Vertex Connectivity Problems
An Interpretation Oriented Theorem Prover over Integers
On the size of homogeneous and of depth four formulas with low individual degree
A full complexity dichotomy for immanant families
Dynamic Trees and Dynamic Point Location (Preliminary Version)
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Multi-processor scheduling to minimize flow time with epsilon resource augmentation
Conditional hardness for satisfiable 3-CSPs
Parallel approximate undirected shortest paths via low hop emulators
Nearly All k-SAT Functions Are Unate
Probabilistic existence of rigid combinatorial structures
Presburger Arithmetic with Bounded Quantifier Alternation
On ACC 0 [ p k ] Frege Proofs
Online service with delay
Fast Monte Carlo Algorithms for Permutation Groups
Optimal Separations Between Concurrent-Write Parallel Machines
The Random Access Hierarchy (Preliminary Report)
Hamiltonian simulation with nearly optimal dependence on spectral norm
Bounded-depth circuits: separating wires from gates
Every Poset Has a Good Comparison
On-line algorithms for cache sharing
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024
Strategic Budget Selection in a Competitive Autobidding World
Average Case Selection
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension
An Algorithm Generating the Decision Table of a Deterministic Bottom Up Parser for a Subset of Context Free Grammars
Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space (Preliminary Version)
Pseudorandom generators for width-3 branching programs