yusuke1997/dblp-id-title huggingface dataset:
Minimum Covers in the Relational Database Model (Extended Abstract)
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs
Beyond NP: the work and legacy of Larry Stockmeyer
Local and Global Expansion in Random Geometric Graphs
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
Block Structure: Retention or Deletion? (Extended Abstract)
Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs
Private Coins versus Public Coins in Interactive Proof Systems
Average-case fine-grained hardness
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Integrality gaps for Sherali-Adams relaxations
A new strategy for querying priced information
Efficient Recovery from Power Outage (Extended Abstract)
Oblivious RAMs without cryptogrpahic assumptions
A Patent Problem for Abstract Programming Languages: Machine-Independent Computations
Making Data Structures Persistent
Breaking the circuit-size barrier in secret sharing
Space-Time Tradeoff for Answering Range Queries (Extended Abstract)
A Logic to Reason about Likelihood
Sparsity Considerations in Dixon Resultants
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Connectivity Labeling and Routing with Multiple Vertex Failures
Testing metric properties
A Data Structure for Dynamic Trees
Cache-oblivious priority queue and graph algorithm applications
Characterizing Linear Size Circuits in Terms of Privacy
Random walks with "back buttons" (extended abstract)
O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
Network Flow and Generalized Path Compression
Approximation algorithms and hardness of integral concurrent flow
A coding theorem for distributed computation
The Complexity of the Matrix Eigenproblem
Fast Algorithms via Dynamic-Oracle Matroids
NP-Complete Decision Problems for Quadratic Polynomials
Algorithms for Capacitated Vehicle Routing
Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems
Polynomial flow-cut gaps and hardness of directed cut problems
Pseudodeterministic algorithms and the structure of probabilistic time
Testing subdivision-freeness: property testing meets structural graph theory
Combining fairness with throughput: online routing with multiple objectives
Linear time low tree-width partitions and algorithmic consequences
Approximating Nash social welfare under rado valuations
An Optimal Sorting Algorithm for Mesh Connected Computers
Solving convex programs by random walks
Capacity lower bound for the Ising perceptron
Asymptotically good Quantum and locally testable classical LDPC codes
L p -testing
Hardness Self-Amplification: Simplified, Optimized, and Unified
Homological product codes
Time-Space-Optimal String Matching
Fast routing table construction using small messages: extended abstract
Multicommodity flow, well-linked terminals, and routing problems
Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
On the complexity of dynamic submodular maximization
All-Pairs Shortest Paths with Few Weights per Node
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
Eliminating intermediate measurements in space-bounded Quantum computation
Efficient deterministic approximate counting for low-degree polynomial threshold functions
Time-adaptive algorithms for synchronization
The Complexity of Control Structures and Data Structures
The Cell Probe Complexity of Dynamic Data Structures
Communication is bounded by root of rank
The Decidability of Distributed Decision Tasks (Extended Abstract)
A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract)
On the complexity of hazard-free circuits
(1 - ε)-Approximation of Knapsack in Nearly Quadratic Time
Base collapse of holographic algorithms
Optimal Bounds for Decision Problems on the CRCW PRAM
Simple parallel algorithms for single-site dynamics
String matching in Lempel-Ziv compressed strings
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
The value of strong inapproximability results for clique
Reducing the Complexity of Reductions
A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
Matrix rigidity of random toeplitz matrices
Minimizing the Flow Time Without Migration
Nonlocality under Computational Assumptions
On approximating the covering radius and finding dense lattice subspaces
Improved approximations of crossings in graph drawings
On maximizing welfare when utility functions are subadditive
Tree-walking automata do not recognize all regular languages
Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
Correlation testing for affine invariant properties on F p n in the high error regime
Computing with continuous-time Liapunov systems
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
Fast sampling and counting k-SAT solutions in the local lemma regime
Efficient two-sided markets with limited information
Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum
Information-theoretic thresholds from the cavity method
Finding smooth integers in short intervals using CRT decoding
A unified analysis of hot video schedulers
Explicit Expanders and the Ramanujan Conjectures
Proving as fast as computing: succinct arguments with constant prover overhead
Non-malleable Reductions and Applications
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract)
Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (Extended Abstract)
Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems
A Framework for Fast Quantum Mechanical Algorithms
Clairvoyant scheduling of random walks
Work efficient parallel solution of Toeplitz systems and polynomial GCD
On the Cryptocomplexity of Knapsack Systems
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
On the advantage over a random assignment
Online vector balancing and geometric discrepancy
The number of minimum k -cuts: improving the Karger-Stein bound
Anti-presistence: history independent data structures
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA
Learning mixtures of arbitrary gaussians
Inference of Finite Automata Using Homing Sequences (Extended Abstract)
Fully dynamic spectral vertex sparsifiers and applications
Voronoi diagrams in n·2 osqrt(lg lg n) time
The network inhibition problem
On the power of quantum fingerprinting
Self-Testing/Correcting with Applications to Numerical Problems
Lossy kernelization
A tight space bound for consensus
Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors
Fast Algorithms under the Extended Riemann Hypothesis: A Concrete Estimate
An Efficient Decoder for a Linear Distance Quantum LDPC Code
New polynomial delay bounds for maximal subgraph enumeration by proximity search
Decision list compression by mild random restrictions
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version)
Quantum Depth in the Random Oracle Model
Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version)
Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
Four Models for the Analysis of Optimization of Program Control Structures
The equivalence of the random oracle model and the ideal cipher model, revisited
O (log 2 k / log log k )-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines
Solving Minimum-Cost Flow Problems by Successive Approximation
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Beyond worst-case analysis in private singular vector computation
An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations
Random Walks on Rotating Expanders
Matroid Products via Submodular Coupling
Bounds for Width Two Branching Programs
Combinatorial construction of locally testable codes
Probabilistic Temporal Logics for Finite and Bounded Models
Non-black-box simulation from one-way functions and applications to resettable security
Efficient Computation on Oblivious RAMs
Data structures meet cryptography: 3SUM with preprocessing
Provable Isomorphisms and Domain Equations in Models of Typed Languages (Preliminary Version)
Homology flows, cohomology cuts
Estimating the weight of metric minimum spanning trees in sublinear-time
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Metric embedding via shortest path decompositions
Iteratively constructing preconditioners via the conjugate gradient method
Computing Integrated Costs of Sequences of Operations with Application to Dictionaries
What can be computed locally?
Don't rush into a union: take time to find your roots
Dynamically Maintaining Configurations in the Plane (Detailed Abstract)
Stochastic bandits robust to adversarial corruptions
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Lower Bounds for the Cycle Detection Problem
Reducing Randomness via Irrational Numbers
Polynomial bounds for the grid-minor theorem
Efficient Reducibility Between Programming Systems: Preliminary Report
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Reinventing the wheel: an optimal data structure for connectivity queries
Finding a Minimum Circuit in a Graph
Fast Approximate PCPs
Approximation algorithm for k-node connected subgraphs via critical graphs
Polynomial-time theory of matrix groups
Load balancing and orientability thresholds for random hypergraphs
Combinatorial optimization problems in self-assembly
With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy
Shadow tomography of quantum states
Privately releasing conjunctions and the statistical query barrier
Fully dynamic approximation of LIS in polylogarithmic time
Learning Polynomial Transformations via Generalized Tensor Decompositions
Collusion resistant traitor tracing from learning with errors
A robust version of Hegedus's lemma, with applications
Explicit two-source extractors and resilient functions
Lower Bounds on the Size of Semidefinite Programming Relaxations
The Complexity of Parallel Evaluation of Linear Recurrence
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Using and Combining Predictors That Specialize
epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract)
An optimal multi-writer snapshot algorithm
Tight dynamic problem lower bounds from generalized BMM and OMv
Approximate clustering via core-sets
A new point of NP-hardness for unique games
Monotone circuits for connectivity have depth (log n) 2-o(1) (Extended Abstract)
Top-k-convolution and the quest for near-linear output-sensitive subset sum
Counting independent sets up to the tree threshold
Randomized versus Deterministic Decision Tree Size
A Fully Dynamic Algorithm for Maintaining the Transitive Closure
Better Trees for Santa Claus
Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k -Median
Decremental single-source reachability in planar digraphs
Comparisons of Polynomial-Time Reducibilities
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020
Exponential Space Complete Problems for Petri Nets and Commutative Semigroups: Preliminary Report
Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
Reducing truth-telling online mechanisms to online optimization
Tensor-rank and lower bounds for arithmetic formulas
Hitting sets with near-optimal error for read-once branching programs
Prediction with a short memory
Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time
Some trade-off results for polynomial calculus: extended abstract
Lattices that admit logarithmic worst-case to average-case connection factors
On the complexity of powering in finite fields
Better extractors for better codes?
Entropy decay in the Swendsen-Wang dynamics on ℤ d
On dynamic range reporting in one dimension
A New Representation for Linear Lists
On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract)
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
Bilateral Trade with Correlated Values
Infinite Games, Randomization, Computability, and Applications to Online Problems (Preliminary Version)
Sublinear time spectral density estimation
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
Approximating the Nash Social Welfare with Indivisible Items
(Almost) tight bounds and existence theorems for confluent flows
Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes
Non-Malleable Cryptography (Extended Abstract)
The DLT priority sampling is essentially optimal
On the Parallel Computation for the Knapsack Problem
Efficient PRAM Simulation on a Distributed Memory Machine
On the All-Pairs-Shortest-Path Problem
Succinct hitting sets and barriers to proving algebraic circuits lower bounds
Real-Time Simulation of Concatenable Double-Ended Queues by Double-Ended Queues (Preliminary Version)
Optimal private halfspace counting via discrepancy
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016
Pareto optimal solutions for smoothed analysts
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Computations with greater quantum depth are strictly more powerful (relative to an oracle)
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
Communication lower bounds for statistical estimation problems via a distributed data processing inequality
Exact algorithms via monotone local search
Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling: Extended Abstract
Geodesic walks in polytopes
A Lower Bound for Parallel String Matching
On Monotone Formulae with Restricted Depth (Preliminary Version)
On Deterministic Approximation of DNF
Entangled Mean Estimation in High Dimensions
Generating Hard Instances of Lattice Problems (Extended Abstract)
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs
Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
The Information Theory Bound Is Tight for Selection in a Heap
On the Locality of the Lovász Local Lemma
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Saving an epsilon: a 2-approximation for the k-MST problem in graphs
Randomly coloring planar graphs with fewer colors than the maximum degree
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2
Semantics and Axiomatics of a Simple Recursive Language
The Distributed Firing Squad Problem (Preliminary Version)
The Space Complexity of Approximating the Frequency Moments
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)
On Formulating Simultaneity for Studying Parallelism and Synchronization
Undirected (1+ ε )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms
Topological Matching
Optimal Algorithms for Byzantine Agreement
Secure computation with information leaking to an adversary
A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems
Scheduling in the Dark
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Improved algorithms via approximations of probability distributions (extended abstract)
Intersecting Is Easier than Sorting
Vertex deletion parameterized by elimination distance and even less
Kalman filtering with adversarial corruptions
Finding minimum-quotient cuts in planar graphs
The Number Field Sieve
Efficient Stable Sorting with Minimal Extra Space
Random Matroids
Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two
A constructive proof of the Lovász local lemma
Unique Maximum Matching Algorithms
Faster suffix tree construction with missing suffix links
Expanders via local edge flips in quasilinear time
Decision Procedures and Expressiveness in the Temporal Logic of Branching Time
The connectivity carcass of a vertex subset in a graph and its incremental maintenance
Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract)
The Pebbling Problem is Complete in Polynomial Space
On Approximability of the Permanent of PSD Matrices
Optimal Proof Systems for Complex Sets Are Hard to Find
Optimal outlier removal in high-dimensional
Edge sampling and graph parameter estimation via vertex neighborhood accesses
Fast matrix rank algorithms and applications
Multilinear formulas and skepticism of quantum computing
Structured recursive separator decompositions for planar graphs in linear time
Constraint satisfaction, packet routing, and the lovasz local lemma
Notes on Merging Networks (Preliminary Version)
A parallel approximation algorithm for positive linear programming
Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract)
Tradeoffs in probabilistic packet marking for IP traceback
Wait-free k-set agreement is impossible: the topology of public knowledge
Quantum entanglement, sum of squares, and the log rank conjecture
Optimal algorithms and inapproximability results for every CSP?
Three-in-a-tree in near linear time
Share-Based Fairness for Arbitrary Entitlements
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA
On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph
Witness encryption and its applications
The Complexity of Backtrack Searches (Preliminary Version)
Quantum One-Time Programs, Revisited
Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Extensions and limits to vertex sparsification
Optimal query complexity bounds for finding graphs
Randomness-Optimal Sampling, Extractors, and Constructive Leader Election
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018
Languages in General Algebras
Efficient Dynamic Programming Using Quadrangle Inequalities
Interpolation of depth-3 arithmetic circuits with two multiplication gates
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
Algorithmic polynomials
A Fast Parallel Algorithm for the Maximal Independent Set Problem
Constructing non-computable Julia sets
Finiteness results for sigmoidal "neural" networks
Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (Extended Abstract)
Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks
Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems
Compatible sequences and a slow Winkler percolation
On Learning Boolean Functions
Green's conjecture and testing linear-invariant properties
Improved Low-Degree Testing and its Applications
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Hashing Schemes for Extendible Arrays (Extended Arrays)
Convex programming for scheduling unrelated parallel machines
Universal Algorithms for Store-and-Forward and Wormhole Routing
Truthful randomized mechanisms for combinatorial auctions
Digital Signets: Self-Enforcing Protection of Digital Information (Preliminary Version)
Dynamic subgraph connectivity with geometric applications
Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report)
Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners
Fast Algorithms for Parametric Scheduling Come from Extensions to Parametric Maximum Flow
Trading Group Theory for Randomness
Two Prover Perfect Zero Knowledge for MIP
A New Graph Triconnectivity Algorithm and Its Parallelization
Quantum one-way communication can be exponentially stronger than classical communication
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Approximating edit distance in near-linear time
Quantitative Steinitz's Theorems with Applications to Multifingered Grasping
Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract)
A sublinear algorithm for weakly approximating edit distance
Recent trends in decentralized cryptocurrencies (invited talk)
From irreducible representations to locally decodable codes
Matching Is as Easy as Matrix Inversion
Probabilistic, Nondeterministic, and Alternating Decision Trees
The Price of Routing Unsplittable Flow
Approximate nearest neighbors and sequence comparison with block operations
Some Unexpected Expected Behavior Results for Bin Packing
Lifting Uniform Learners via Distributional Decomposition
Fitting algebraic curves to noisy data
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
Linear probing with constant independence
Optimal rate-based scheduling on multiprocessors
Approximate Graph Colouring and the Hollow Shadow
Using nondeterminism to amplify hardness
Improved Dynamic Colouring of Sparse Graphs
Almost All Primes Can Be Quickly Certified
Lee-Yang theorems and the complexity of computing averages
An Improved Parameterized Algorithm for Treewidth
Sparsest cut on bounded treewidth graphs: algorithms and hardness results
An improved cutting plane method for convex optimization, convex-concave games, and its applications
The structure of optimal private tests for simple hypotheses
Fourier meets möbius: fast subset convolution
Two Infinite Sets of Primes with Fast Primality Tests
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
Finding approximate local minima faster than gradient descent
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
An Efficient Signature Scheme Based on Quadratic Equations
Optimal euclidean spanners: really short, thin and lanky
A sparse Johnson: Lindenstrauss transform
Short random walks on graphs
Lattice problems and norm embeddings
Stability of service under time-of-use pricing
Trapdoors for hard lattices and new cryptographic constructions
Tight bounds for distributed functional monitoring
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
A unified approach to approximating resource allocation and scheduling
Complexity Classes of Partial Recursive Functions (Preliminary Version)
Complete fairness in secure two-party computation