yusuke1997/dblp-id-title huggingface dataset:
Worst-Case Analysis of Memory Allocation Algorithms
On the Power of Homogeneous Algebraic Formulas
Parallel exhaustive search without coordination
Efficient splitting off algorithms for graphs
Optimal Non-adaptive Tolerant Junta Testing via Local Estimators
Turing Machines and the Spectra of First-Order Formulas with Equality
A characterization of approximability for biased CSPs
A Useful Device for Showing the Solvability of Some Decision Problems
Iterated lower bound formulas: a diagonalization-based approach to proof complexity
Fingerprinting codes and the price of approximate differential privacy
Non-malleable extractors and codes, with their many tampered extensions
Simple and Efficient Bounded Concurrent Timestamping or Bounded Concurrent Timestamp Systems are Comprehensible!
The Undecidability of the Semi-Unification Problem (Preliminary Report)
Absolutely Parallel Grammars and Two-Way Deterministic Finite-State Transducers
Breaching the 2-approximation barrier for the forest augmentation problem
On Approximating Arbitrary Metrices by Tree Metrics
Differential privacy for the analyst via private equilibrium computation
Economical Solutions for the Critical Section Problem in a Distributed System (Extended Abstract)
The Quantum Query Complexity of Approximating the Median and Related Statistics
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling
On partitioning graphs via single commodity flows
Adiabatic quantum state generation and statistical zero knowledge
A Probabilistic PDL
Graph limits and parameter testing
Limitations of Stochastic Selection Problems with Pairwise Independent Priors
Private Information Storage (Extended Abstract)
Decision trees: old and new results
Two applications of information complexity
An exponential lower bound on the sub-packetization of MSR codes
Nearly Optimal Fault Tolerant Distance Oracle
On point location and motion planning among simplices
On Some Generalizations of Binary Search
Interactive coding over the noisy broadcast channel
Towards optimal lower bounds for k-median and k-means coresets
Testing graphs in vertex-distribution-free models
Quantum computers that can be simulated classically in polynomial time
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA
Combinatorial Correlation Clustering
Settling the complexity of Nash equilibrium in congestion games
Adaptive and Oblivious Statistical Adversaries Are Equivalent
A strongly polynomial algorithm for bimodular integer linear programming
An optimal separation of randomized and Quantum query complexity
A generalized Turán problem and its applications
Constant-round interactive proofs for delegating computation
Some complexity issues on the simply connected regions of the two-dimensional plane
Classical hardness of learning with errors
Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
Multi-agent Contracts
Quantum Circuits with Mixed States
Computing with Unreliable Information (Preliminary Version)
Oblivious Data Structures: Applications to Cryptography
Hidden Surface Removal with Respect to a Moving View Point
Finding Euler Circuits in Logarithmic Parallel Time
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs
Testing versus estimation of graph properties
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
Testing Graph Connectivity
A polylog( n )-Competitive Algorithm for Metrical Task Systems
The threshold for random k-SAT is 2 k (ln 2 - O(k))
Matrix discrepancy from Quantum communication
Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract)
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
Adversarial laws of large numbers and optimal regret in online classification
Pauli Measurements Are Not Optimal for Single-Copy Tomography
A Characterization of the Capacity of Online (causal) Binary Channels
The distance trisector curve
Time-Space Trade-Offs for Asynchronous Parallel Models: Reducibilities and Equivalences
On-Line Algorithms for Steiner Tree Problems (Extended Abstract)
Walking randomly, massively, and efficiently
Robust moment estimation and improved clustering via sum of squares
One-Way Functions are Necessary and Sufficient for Secure Signatures
Efficient Program Transformations for Resilient Parallel Computation via Randomization (Preliminary Version)
A Completeness Technique for D-Axiomatizable Semantics
A Hierarchy for Nondeterministic Time Complexity
Multicasting in Heterogeneous Networks
Size-Time Complexity of Boolean Networks for Prefix Computations
Dynamic planar point location in optimal time
Self-Testing/Correcting for Polynomials and for Approximate Functions
Riemann Hypothesis and Finding Roots over Finite Fields
Connectivity oracles for failure prone graphs
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
An improved approximation algorithm for the minimum k -edge connected multi-subgraph problem
Output Sensitive Construction of Levels and Voronoi Diagrams in R^d of Order 1 to k
Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
Near-optimal network design with selfish agents
Near-optimal extractors against quantum storage
How to Use Quantum Indistinguishability Obfuscation
Explicit binary tree codes with sub-logarithmic size alphabet
Fast leader-election protocols with bounded cheaters' edge
Swap Cosystolic Expansion
A new algorithm for Euclidean shortest paths in the plane
Some Restrictions on W-Grammars
Solving linear programs in the current matrix multiplication time
On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version)
Profit-earning facility location
On the submodularity of influence in social networks
A Correctness Condition for High-Performance Multiprocessors (Extended Abstract)
On Different Modes of Communication (Extended Abstract)
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs
Optimizing tree pattern queries: why cutting is not enough (invited talk)
Operator scaling with specified marginals
Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines
Quantified derandomization of linear threshold circuits
Space-efficient scheduling of multithreaded computations
Combinatorial complexity in O-minimal geometry
On Extracting Randomness From Weak Random Sources (Extended Abstract)
Learning Ising models from one or multiple samples
Black-box identity testing of depth-4 multilinear circuits
Many sparse cuts via higher eigenvalues
On the complexity of two-party differential privacy
Backing Up in Singly Linked Lists
Lower bounds for parallel linear programming and other problems
The Complexity of Satisfiability Problems
Approximation resistance from pairwise independent subgroups
Privacy-preserving statistical estimation with optimal convergence rates
No self-concordant barrier interior point method is strongly polynomial
Deterministic and probabilistic binary search in graphs
Coping with Errors in Binary Search Procedures (Preliminary Report)
Provable learning of noisy-OR networks
Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)
Prophet Inequalities Require Only a Constant Number of Samples
A deterministic algorithm for the three-dimensional diameter problem
Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract
Finding red balloons with split contracts: robustness to individuals' selfishness
Optimal Precision in the Presence of Uncertainty (Preliminary Version)
Extractor codes
A Decidable Propositional Probabilistic Dynamic Logic
Strong XOR Lemma for Information Complexity
Models and thresholds for random constraint satisfaction problems
Equivalence of deterministic one-counter automata is NL-complete
Minimax parametric optimization problems and multi-dimensional parametric searching
Geometric median in nearly linear time
Faster Rates for No-Regret Learning in General Games via Cautious Optimism
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
Extensor-coding
Geometry Helps in Matching (Extended Abstract)
Sorting under partial information (without the ellipsoid algorithm)
A PTAS for unsplittable flow on a path
Complexity classification of counting graph homomorphisms modulo a prime number
An Approach to The k Paths Problem
On the searchability of small-world networks with arbitrary underlying structure
Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups
Unique games on expanding constraint graphs are easy: extended abstract
Beating CountSketch for heavy hitters in insertion streams
List-decoding reed-muller codes over small fields
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling
Post-quantum zero knowledge in constant rounds
Lower Bounds for Non-Commutative Computation (Extended Abstract)
Pseudo-random Permutation Generators and Cryptographic Composition
RL ⊆ SC
Maximum Bipartite Matching in n 2+o(1) Time via a Combinatorial Algorithm
Fault Tolerance of Minimal Path Routings in a Network
Simple deterministic approximation algorithms for counting matchings
On the Expected Behaviour of Disjoint Set Union Algorithms
Reconstruction of non-degenerate homogeneous depth three circuits
Improved distributed algorithms for exact shortest paths
Parallel Symmetry-Breaking in Sparse Graphs
The sample complexity of auctions with side information
Efficient rounding for the noncommutative grothendieck inequality
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
The Effect of Updates in Binary Search Trees
Typical properties of winners and losers in discrete optimization
Deterministic Simulation in LOGSPACE
Low-rank approximation with 1/ε 1/3 matrix-vector products
Finding Similar Regions in Many Strings
Local list-decoding and testing of random linear codes from high error
Tight time-space tradeoff for mutual exclusion
Non-approximability results for optimization problems on bounded degree instances
Trickle-Down in Localization Schemes and Applications
An area law for 2d frustration-free spin systems
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs
Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity
Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
Fast Algorithms for k -Shredders and k -Node Connectivity Augmentation (Extended Abstract)
What's decidable about hybrid automata?
Time-Bounded Random Access Machines
Finding sparse cuts locally using evolving sets
Fast algorithms for finding randomized strategies in game trees
A Complete Axiomatic System for Proving Deductions about Recursive Programs
Random lattice triangulations: structure and algorithms
Capacity upper bounds for deletion-type channels
Linear time construction of compressed text indices in compact space
Augmenting undirected node-connectivity by one
Strongly refuting random CSPs below the spectral threshold
Design Networks with Bounded Pairwise Distance
Classification of Computable Functions by Primitive Recursive Classes
Factoring Multivariate Polynomials over Finite Fields (Extended Abstract)
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
The Complexity of Elementary Algebra and Geometry (Preliminary Abstract)
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
An efficient algorithm for solving word equations
Composable and versatile privacy via truncated CDP
Candidate hard unique game
Learning general halfspaces with general Massart noise under the Gaussian distribution
Algorithmic Bayesian persuasion
Two lower bounds for branching programs
Nondeterminism and the Size of Two Way Finite Automata
Limitations of Synchronization Primitives with Conditional Branching and Global Variables
Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games
Parallel Algorithms for the Transitive Closure and the Connected Component Problems
A strong direct product theorem for disjointness
Low distortion maps between point sets
On the sum-of-squares algorithm for bin packing
Optimal Explicit Small-Depth Formulas for the Coin Problem
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
Vanishing of Schubert Coefficients
Cover times, blanket times, and majorizing measures
Pseudorandom Generators Without the XOR Lemma (Extended Abstract)
Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation
Recognition of graphs with threshold dimension two
Pseudorandom generators for combinatorial shapes
Analysis of a Classical Matrix Preconditioning Algorithm
Approximate Gomory-Hu tree is faster than n - 1 max-flows
Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers
Trees and Euclidean Metrics
Expander random walks: a Fourier-analytic approach
On the Faithful Regular Extensions of Iterative Algebras
Near Optimal Alphabet-Soundness Tradeoff PCPs
The next 700 network programming languages (invited talk)
An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
The communication complexity of interleaved group products
Design extractors, non-malleable condensers and privacy amplification
Geometric lower bounds for parametric matroid optimization
Optimal Rounding for Sparsest Cut
Trade-offs between communication throughput and parallel time
Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract)
Subtree Replacement Systems: A Unifying Theory for Recursive Equations, LISP, Lucid and Combinatory Logic
Learning Shallow Quantum Circuits
Near-optimal sparse fourier representations via sampling
Support of closed walks and second eigenvalue multiplicity of graphs
Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
Interaction is necessary for distributed learning with privacy or communication constraints
Fast algorithms for knapsack via convolution and prediction
Multicommodity Flows in Planar Undirected Graphs and Shortest Paths
Approximating the exponential, the lanczos method and an Õ( m )-time spectral algorithm for balanced separator
Nondeterministic Communication with a Limited Number of Advice Bits
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Kraft Storage and Access for List Implementations (Extended Abstract)
Quantum state certification
Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (Extended Abstract)
Isomorphism testing for embeddable graphs through definability
Recursion Schemes with Lists
Statistical query complexity of manifold estimation
Nearly work-efficient parallel algorithm for digraph reachability
Distributed Quantum Advantage for Local Problems
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns
Average case analysis for batched disk scheduling and increasing subsequences
Coresets in dynamic geometric data streams
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
Provisioning a virtual private network: a network design problem for multicommodity flow
Ensembles Reconnaissables de Mots Biinfinis
Faster Deterministic Distributed MIS and Approximate Matching
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes
Sylvester-Gallai type theorems for quadratic polynomials
Quantum Advantage from Soft Decoders
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Improved approximation for tree augmentation: saving by rewiring
Byzantine Quorum Systems
Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems
A Layout Strategy for VLSI which Is Provably Good (Extended Abstract)
A PCP characterization of NP with optimal amortized query complexity
Pseudo-random generators for all hardnesses
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs
Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract)
Sorting and searching in the presence of memory faults (without redundancy)
Deterministic decremental single source shortest paths: beyond the o(mn) bound
Finding small balanced separators
Improved Bounds for Testing Low Stabilizer Complexity States
The Round Complexity of Statistical MPC with Optimal Resiliency
Resolution lower bounds for the weak pigeonhole principle
Uncloneable Quantum States Are Necessary as Proofs and Advice
Property testing in hypergraphs and the removal lemma
Parallel repetition in projection games and a concentration bound
Decremental strongly-connected components and single-source reachability in near-linear time
Regret minimization and the price of total anarchy
Games for exchanging information
Robustly learning mixtures of k arbitrary Gaussians
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
A quasipolynomial (2 + ε )-approximation for planar sparsest cut
Optimal approximation for the submodular welfare problem in the value oracle model
Towards a Syntactic Characterization of PTAS
The asynchronous computability theorem for t-resilient tasks
Sketching and Embedding are Equivalent for Norms
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time
Approximation Algorithms for the Geometric Multimatching Problem
Finding topological subgraphs is fixed-parameter tractable
2 log1-ε n hardness for the closest vector problem with preprocessing
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
A fully-dynamic data structure for external substring search (Extended Abstract)
Spectral Hypergraph Sparsification via Chaining
epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract)
Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
Tensor decomposition and approximation schemes for constraint satisfaction problems
Normal Forms for Trivalent Graphs and Graphs of Bounded Valence
Online load balancing on related machines
The Logical Complexity of Geometric Properties in the Plane
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Improved bounds for the sunflower lemma
Packing Even Directed Circuits Quarter-Integrally
Tighter bounds for nearest neighbor search and related problems in the cell probe model
A Constant-Time Optimal Parallel String-Matching Algorithm
Improved non-approximability results
Tree embeddings for hop-constrained network design
From query complexity to computational complexity
Graph Pebbling with Many Free Pebbles can be Difficult
On the impossibility of a quantum sieve algorithm for graph isomorphism
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Vertex connectivity in poly-logarithmic max-flows
A New Approach to Learning Linear Dynamical Systems
Optimal oblivious routing in polynomial time
The polynomial method strikes back: tight quantum query bounds via dual polynomials
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015
Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity
Balanced Matroids
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices
Context-Sensitive Immediate Constituent Analysis-Context-Free Languages Revisited
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA
Pseudorandomness for network algorithms
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Integer priority queues with decrease key in constant time and the single source shortest paths problem
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)
Approximate Inclusion-Exclusion
Product-state approximations to quantum ground states
Network games
Transformations and Translations from the Point of View of Generalized Finite Automata Theory
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
No Distributed Quantum Advantage for Approximate Graph Coloring
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
The k-Steiner ratio in graphs
On Effective Procedures for Speeding Up Algorithms
Running time and program size for self-assembled squares
Exact and Approximate Membership Testers
Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation
Near-optimal linear decision trees for k-SUM and related problems
Better Bounds for Online Scheduling
Communication in the presence of replication
Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
Universal Circuits (Preliminary Report)
An Algebraic Theory of Recursive Definitions and Recursive Languages
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
Competitive Algorithms for Distributed Data Management (Extended Abstract)
Towards a Theory of Semantics and Compilers for Programming Languages
Pseudo-random functions and factoring (extended abstract)
Short path queries in planar graphs in constant time
New algorithms and hardness for incremental single-source shortest paths in directed graphs
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract)
On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Finding nearest neighbors in growth-restricted metrics
An accelerated interior point method whose running time depends only on A (extended abstract)
The mixing time of the Thorp shuffle
Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut
Online Locality Meets Distributed Quantum Computing
Testing surface area with arbitrary accuracy
Euclidean distortion and the sparsest cut
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Two heads are better than two tapes
Efficient asynchronous distributed symmetry breaking
Algorithmic Complexity in Coding Theory and the Minimum Distance Problem
Proportionate progress: a notion of fairness in resource allocation
Efficient construction of directed hopsets and parallel approximate shortest paths
Span-program-based quantum algorithm for evaluating formulas
The program-size complexity of self-assembled paths
Locality Bounds for Sampling Hamming Slices
A New Approach to the Maximum Flow Problem
Symmetric Exponential Time Requires Near-Maximum Circuit Size
New bounds for matching vector families
An efficient parallel solver for SDD linear systems
Structural Complexities of Matching Mechanisms
The Analysis of Double Hashing (Extended Abstract)
Efficiency improvements in constructing pseudorandom generators from one-way functions
Closure of Families of Languages under Substitution Operators
Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders
Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract)
Polynomial Evaluation via the Division Algorithm: The Fast Fourier Transform Revisited