yusuke1997/dblp-id-title huggingface dataset:
Obfuscation of Pseudo-Deterministic Quantum Circuits
Wait-free Parallel Algorithms for the Union-Find Problem
Query strategies for priced information (extended abstract)
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Correct and Optimal Implementations of Recursion in a Simple Programming Language
An Analysis of the Full Alpha-Beta Pruning Algorithm
A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines
Sampling-based dimension reduction for subspace approximation
A Generalization and Proof of the Aanderaa-Rosenberg Conjecture
Space-Bounded Hierarchies and Probabilistic Computations
The Care and Feeding of LR(k) Grammars
Interior Point Methods with a Gradient Oracle
2-Server PIR with Sub-Polynomial Communication
Certified Randomness from Quantum Supremacy
Evaluating Logarithms in GF(2^n)
Approximate max-integral-flow/min-multicut theorems
Matrix Multiplication via Arithmetic Progressions
Bounded-error quantum state identification and exponential separations in communication complexity
Better Approximation for Weighted k-Matroid Intersection
Clustered Integer 3SUM via Additive Combinatorics
Separating succinct non-interactive arguments from all falsifiable assumptions
Reconstruction for the Potts model
Improved approximation algorithms for uniform connectivity problems
The FPᴺᴾ versus #P Dichotomy for #EO
Developmental Systems and Languages
The communication complexity of local search
K -sat on Groups and Undecidability
An extendable data structure for incremental stable perfect hashing
A new average case analysis for completion time scheduling
Maximum k-chains in planar point sets: combinatorial structure and algorithms
A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension
Improved Routing and Sorting on Multibutterflies
A shorter proof of the graph minor algorithm: the unique linkage theorem
Randomized Composable Core-sets for Distributed Submodular Maximization
Simulating threshold circuits by majority circuits
Tree Transducers, L Systems and Two-Way Machines (Extended Abstract)
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
The List Decoding Radius of Reed-Muller Codes over Small Fields
Fast asynchronous Byzantine agreement with optimal resilience
Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions
The Two-Processor Scheduling Problem is in R-NC
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
Faster maxflow via improved dynamic spectral vertex sparsifiers
Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields
Single-Copy Stabilizer Testing
The complexity of splitting necklaces and bisecting ham sandwiches
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
The loss of serving in the dark
Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
Computing a nonnegative matrix factorization - provably
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Paul Erdös (1913-1996): His Influence on the Theory of Computing
A characterization of locally testable affine-invariant properties via decomposition theorems
On the cell probe complexity of membership and perfect hashing
Exploiting Regularities in Web Traffic Patterns for Cache Replacement
Better secret sharing via robust conditional disclosure of secrets
How much can hardware help routing?
Fault tolerant subgraph for single source reachability: generic and optimal
Excluded minors, network decomposition, and multicommodity flow
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
On the composition of authenticated byzantine agreement
Balanced allocations (extended abstract)
No Complete Problem for Constant-Cost Randomized Communication
A strongly polynomial algorithm for linear exchange markets
Kolmogorov complexity version of Slepian-Wolf coding
Interactive privacy via the median mechanism
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads
Extractors for a constant number of polynomially small min-entropy independent sources
Improving exhaustive search implies superpolynomial lower bounds
Toward a Non-Atomic Era: \ell-Exclusion as a Test Case
I/O Complexity: The Red-Blue Pebble Game
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
Graph entropy and quantum sorting problems
Randomness conductors and constant-degree lossless expanders
The extended BG-simulation and the characterization of t-resiliency
Euclidean spanners: short, thin, and lanky
Minimizing average flow time on related machines
Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract)
A Characterization of List Learnability
Competitively chasing convex bodies
Approximate distance oracles
On the Power of Interactive Proofs for Learning
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract
Approximately Counting Up To Four (Extended Abstract)
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems
Implicit O(1) Probe Search
Self-Improvement for Circuit-Analysis Problems
Breaking the quadratic barrier for matroid intersection
Randomized Omega(n 2 ) Lower Bound for Knapsack
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Some 3CNF properties are hard to test
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Expressiveness of Restricted Recursive Queries (Extended Abstract)
Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits
Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm
A combinatorial, primal-dual approach to semidefinite programs
Explicit binary tree codes with polylogarithmic size alphabet
An almost-linear time algorithm for uniform random spanning tree generation
On the Extended Direct Sum Conjecture
The Rate of Interactive Codes Is Bounded Away from 1
Multi-armed bandits in metric spaces
A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
A sieve algorithm for the shortest lattice vector problem
Algorithms for stable and perturbation-resilient problems
Planar Map Graphs
On Optimal Coreset Construction for Euclidean (k, z)-Clustering
Zero Knowledge Proofs of Identity
Simple deterministic algorithms for fully dynamic maximal matching
Testing Finite State Machines (Extended Abstract)
Fault Tolerant Planar Communication Networks
Approximating s-t Minimum Cuts in Õ ( n 2 ) Time
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
Recognizing string graphs in NP
Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set
Algebraic property testing: the role of invariance
On contention resolution protocols and associated probabilistic phenomena
Interaction in quantum communication and the complexity of set disjointness
Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees
Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True
Lifting to Bounded-Depth and Regular Resolutions over Parities via Games
The Tight Deterministic Time Hierarchy
On uniform amplification of hardness in NP
A New Fixed Point Approach for Stable Networks and Stable Marriages
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA
Testing graphs against an unknown distribution
New degree bounds for polynomial threshold functions
Linear-time encodable and decodable error-correcting codes
Polynomial space polynomial delay algorithms for listing families of graphs
Random walks and forbidden minors II: a poly( d ε -1 )-query tester for minor-closed properties of bounded degree graphs
Linear space streaming lower bounds for approximating CSPs
Communication Lower Bounds for Collision Problems via Density Increment Arguments
On Abstractions of Parallel Programs
Two Tapes Are Better than One for Off-Line Turing Machines
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Quasi-Linear Size PCPs with Small Soundness from HDX
Load balancing with dynamic set of balls and bins
Deterministic Selection in O(log log N) Parallel Time
An invariance principle for polytopes
Prize-Collecting Steiner Tree: A 1.79 Approximation
Comparison-based search in the presence of errors
Solvability by Radicals is in Polynomial Time
A polynomial quantum algorithm for approximating the Jones polynomial
Time-space trade-offs for undirected st-connectivity on a JAG
Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses
Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation
From Independence to Expansion and Back Again
How asymmetry helps buffer management: achieving optimal tail size in cup games
Fooling polytopes
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
Embedding and canonizing graphs of bounded genus in logspace
OPT versus LOAD in dynamic storage allocation
Almost Optimal PAC Learning for k-Means
Online Algorithms for Locating Checkpoints
A new approach to dynamic all pairs shortest paths
The relative complexity of NP search problems
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Covering Points in the Plane by k -Tours: Towards a Polynomial Time Approximation Scheme for General k
Concurrent Zero-Knowledge
Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption
On lazy randomized incremental construction
Quantum vs. Classical Communication and Computation
Reconstructing a Three-Dimensional Model with Arbitrary Errors
The geometry of differential privacy: the sparse and approximate cases
Pseudorandom generators with long stretch and low locality from random local one-way functions
Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions
Memory bounds for the experts problem
NP-hardness of approximately solving linear equations over reals
Multi-parameter mechanism design and sequential posted pricing
MaxMin allocation via degree lower-bounded arborescences
Competitive Paging with Locality of Reference (Preliminary Version)
Analyze gauss: optimal bounds for privacy-preserving principal component analysis
Fast integer multiplication using modular arithmetic
Mapping the genome: some combinatorial problems arising in molecular biology
The Complexity of Relational Query Languages (Extended Abstract)
Optimal path search in small worlds: dimension matters
Sparse Quantum Codes from Quantum Circuits
Short Proofs are Narrow - Resolution Made Simple
Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing
Correlated Pseudorandomness and the Complexity of Private Computations
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems
The Santa Claus problem
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
A friendly smoothed analysis of the simplex method
On approximating the number of k-cliques in sublinear time
The Complexity of Problems in Systems of Communicating Sequential Processes (Extended Abstract)
The freezing threshold for k-colourings of a random graph
Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications
Near-optimal algorithms for unique games
More theory revision with queries (extended abstract)
A near optimal algorithm for edge separators (preliminary version)
The Complexity of the Equivalence Problem for Straight-Line Programs
PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
On Floorplans of Planar Graphs
Testing of the Long Code and Hardness for Clique
On the list-decodability of random linear codes
Discrepancy Algorithms for the Binary Perceptron
The reachability problem for Petri nets is not elementary
Adaptive Approximation Schemes for Matching Queues
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
Efficient discrete-time simulations of continuous-time quantum query algorithms
On the Size of Programs in Subrecursive Formalisms
A Characterization of the Power of Vector Machines
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper)
Polynomial time quantum algorithm for the computation of the unit group of a number field
Simultaneous auctions are (almost) efficient
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Distributed ∆-coloring plays hide-and-seek
Every list-decodable code for high noise has abundant near-optimal rate puncturings
Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of their Circuits
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Robust pcps of proximity, shorter pcps and applications to coding
Breaking the T^(2/3) Barrier for Sequential Calibration
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max
Local max-cut in smoothed polynomial time
Hitting topological minors is FPT
Streaming algorithms for embedding and computing edit distance in the low distance regime
The Random Oracle Methodology, Revisited (Preliminary Version)
Lower bounds for local search by quantum arguments
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Stochastic combinatorial optimization via poisson approximation
Eigenvalues, Flows and Separators of Graphs
Hidden translation and orbit coset in quantum computing
Algorithms for minimizing weighted flow time
Stable Prehension with Three Fingers
Automata, circuits and hybrids: facets of continuous time
Textbook non-malleable commitments
On the Theory of Average Case Complexity
Fast Parallel Processing Array Algorithms for some Graph Problems (Preliminary Version)
Statistical physics of random CSPs (tutorial)
Computing simple mechanisms: Lift-and-round over marginal reduced forms
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)
On Approximability of Satisfiable k-CSPs: V
Public-key cryptography from different assumptions
Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication
Separator based sparsification for dynamic planar graph algorithms
Computing Nash equilibria for scheduling on restricted parallel links
Variations on Pushdown Machines (Detailed Abstract)
Measures of Parallelism in Alternating Computation Trees (Extended Abstract)
Automating cutting planes is NP-hard
Interval completion with few edges
Approximating the smallest grammar: Kolmogorov complexity in natural models
The multiparty communication complexity of set disjointness
Interactive error resilience beyond 2/7
Monotone Circuits for Matching Require Linear Depth
Spot-Checkers
Improved iteration complexities for overconstrained p -norm regression
Computing faces in segment and simplex arrangements (Preliminary Version)
Testing subgraphs in directed graphs
Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹
Distribution-free junta testing
Breaking the O(m 2 n)-Time Barrier for Vertex-Weighted Global Minimum Cut
The communication complexity of uncoupled nash equilibrium procedures
A constant-factor approximation for stochastic Steiner forest
The power of factorization mechanisms in local and central differential privacy
Extractors for adversarial sources via extremal hypergraphs
More consequences of falsifying SETH and the orthogonal vectors conjecture
Flowchart Schemata with Counters
White Pebbles Help
An effective ergodic theorem and some applications
Intersection-Closed full AFL and the Recursively Enumerable Languages
Girth and euclidean distortion
Learning submodular functions
Bounding the power of preemption in randomized scheduling
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
Reference Machines Require Non-linear Time to Maintain Disjoint Sets
Multi-collision resistance: a paradigm for keyless hash functions
Almost-optimal sublinear-time edit distance in the low distance regime
Pseudorandom generators for group products: extended abstract
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching
Some NP-Complete Geometric Problems
Approximation algorithms for network design with metric costs
Smoothed Analysis for Graph Isomorphism
Zero knowledge with efficient provers
Low rank approximation with entrywise l 1 -norm error
Near-optimal distributed degree+1 coloring
The online set cover problem
Expander flows, geometric embeddings and graph partitioning
A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
Improved approximation guarantees for minimum-weight k -trees and prize-collecting salesmen
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
On oblivious PTAS's for nash equilibrium
Memory-sample tradeoffs for linear regression with small error
Conditional hardness for approximate coloring
Lower bounds for depth 4 formulas computing iterated matrix multiplication
Quadratic forms on graphs
Target Shooting with Programmed Random Variables
Linear Hashing Is Optimal
Structure of Complexity in the Weak Monadic Second-Order Theories of the Natural Numbers
Communication-Efficient Parallel Sorting (Preliminary Version)
A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
Decidable Optimization Problems for Database Logic Programs (Preliminary Report)
Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
A new multilayered PCP and the hardness of hypergraph vertex cover
A Subexponential Randomized Simplex Algorithm (Extended Abstract)
Pushdown Store Machines and Real-Time Computation
Ghost Value Augmentation for k-Edge-Connectivity
Approximating permanents of complex matrices
NP Is as Easy as Detecting Unique Solutions
Low-rank matrix completion using alternating minimization
Recognizing well-parenthesized expressions in the streaming model
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities
An improved LP-based approximation for steiner tree
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version)
A matrix expander Chernoff bound
Sherali-adams relaxations of the matching polytope
A strong version of Cobham's theorem
Independence Results in Computer Science? (Preliminary Version)
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract)
On the Complexity of the Theories of Weak Direct Products: A Preliminary Report
NLTS Hamiltonians from Good Quantum Codes
A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture
Consensus halving is PPA-complete
Evaluation of Polynomials with Super-Preconditioning
Erratum for: on basing one-way functions on NP-hardness
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
The Entropic Limitations on VLSI Computations (Extended Abstract)
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)
Exponential Lower Bounds for Depth 3 Boolean Circuits
The Complexity of Approximate Counting (Preliminary Version)
Improved cryptographic hash functions with worst-case/average-case connection
Efficient and near-optimal algorithms for sampling connected subgraphs
Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version)
A quantum linearity test for robustly verifying entanglement
Non-adaptive adaptive sampling on turnstile streams
Removal lemmas with polynomial bounds
Retraction of Probabilistic Computation and Linear Time
Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract)
Optimal Non-oblivious Open Addressing
The Power of Adaptivity in Quantum Query Algorithms
Testing noisy linear functions for sparsity
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sampling constraint satisfaction solutions in the local lemma regime
The importance of being biased
Bandwidth allocation with preemption
Routing in undirected graphs with constant congestion
The gram-schmidt walk: a cure for the Banaszczyk blues
Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
Every minor-closed property of sparse graphs is testable
A simply exponential upper bound on the maximum number of stable matchings
Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs
Noise-tolerant learning, the parity problem, and the statistical query model
Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013
Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, May 1-3, 1972, Denver, Colorado, USA
Optimal vertex connectivity oracles
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
Low-end uniform hardness vs. randomness tradeoffs for AM
Errata to "How hard is to marry at random? (On the approximation of the permanent)"
Simplicity creates inequity: implications for fairness, stereotypes, and interpretability (invited paper)
The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs
Testing Cluster Structure of Graphs
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets
On Isomorphisms and Density of NP and Other Complete Sets
Why prices need algorithms (invited talk)
A Bound on the Quantum Value of All Compiled Nonlocal Games
Balanced max 2-sat might not be the hardest
Fully-dynamic planarity testing in polylogarithmic time
Expanders from symmetric codes
Fast hamiltonicity checking via bases of perfect matchings
Beyond the low-degree algorithm: mixtures of subcubes and their applications
On k-hulls and Related Problems
Separating the communication complexity of truthful and non-truthful combinatorial auctions
Private matchings and allocations
Computing Frobenius Maps and Factoring Polynomials (Extended Abstract)
Reusable garbled circuits and succinct functional encryption