yusuke1997/dblp-id-title huggingface dataset:
A Threshold of ln n for Approximating Set Cover (Preliminary Version)
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Sampling and Integration of Near Log-Concave functions
An Efficient Algorithm for Determining Whether a Cubic Graph is Toroidal
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Testing multivariate linear functions: overcoming the generator bottleneck
Computational complexity of the ground state energy density problem
Some Structural Properties of Polynomial Reducibilities and Sets in NP
Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments
Enumerating parametric global minimum cuts by random interleaving
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications
Computing crossing number in linear time
Uniformly Random Colourings of Sparse Graphs
On Shortest Paths in Polyhedral Spaces
Exponential communication separations between notions of selfishness
The work of Leslie Valiant
How robust are reconstruction thresholds for community detection?
A new greedy approach for facility location problems
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
On the limits of cache-obliviousness
Average-case lower bounds for formula size
Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)
Negative weights make adversaries stronger
How to match when all vertices arrive online
Tight bounds for asynchronous randomized consensus
Robustness of average-case meta-complexity via pseudorandomness
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Non-standard stringology: algorithms and complexity
Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract)
Perfect Zero-Knowledge in Constant Rounds
Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
Optimal succinct rank data structure via approximate nonnegative tensor decomposition
Tight analyses of two local load balancing algorithms
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
Lower bounds for k-DNF resolution on random 3-CNFs
The quantum adiabatic optimization algorithm and local minima
Semidefinite programs on sparse random graphs and their application to community detection
Unconditional differentially private mechanisms for linear queries
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
Algebraic Structure Theory of Stochastic Machines
Algorithms for Rational Function Arithmetic Operations
Sparsity lower bounds for dimensionality reducing maps
Efficient Algorithms and New Characterizations for CSP Sparsification
On Indexed Data Broadcast
An improved approximation algorithm for ATSP
Asymptotic Conditional Probabilities for First-Order Logic
An Iteration Theorem for One-Counter Languages
Three Theorems on Abstract Families of Languages
Program Schemas with Equality
Polynomial Reducibilities and Upward Diagonalizations
Packet Routing with Arbitrary End-to-End Delay Requirements
Almost tight bounds for rumour spreading with conductance
The Joy of Theory
On the Cryptographic Security of Single RSA Bits
Separations in query complexity using cheat sheets
Compression and Ranking
Convex Decompositions of Polyhedra
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap
Real-Time Algorithms for String-Matching and Palindrome Recognition
Deadlock-Free Packet Switching Networks
Advances in metric embedding theory
Matroid matching: the power of local search
Finding long paths and cycles in sparse Hamiltonian graphs
Entanglement subvolume law for 2d frustration-free spin systems
Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA
A Simple Three-Dimensional Real-Time Reliable Cellular Array
Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract)
Euler paths in series parallel graphs
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA
Randomized communication and implicit graph representations
Equivalence of Relational Database Schemes
Reconfiguration of Basis Pairs in Regular Matroids
Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information
Subrecursive Program Schemata I & II: I. Undecidable Equivalence Problems; II. Decidable Equivalence Problems
A new coreset framework for clustering
Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
The vpn conjecture is true
Tight query complexity lower bounds for PCA via finite sample deformed wigner law
Approximation algorithms for deadline-TSP and vehicle routing with time-windows
The Power of a Pebble: Exploring and Mapping Directed Graphs
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
(1+epsilon, beta)-spanner constructions for general graphs
Finding the Median Requires 2n Comparisons
Towards coding for maximum errors in interactive communication
On Relationships between Statistical Zero-Knowledge Proofs
Indistinguishability obfuscation from circular security
An exponential separation between regular and general resolution
Polylog-Competitive Deterministic Local Routing and Scheduling
Explicit Codes Approaching Generalized Singleton Bound using Expanders
Some new results on node-capacitated packing of A-paths
Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
An Optimal Algorithm for On-line Bipartite Matching
From Signaling to Interviews in Random Matching Markets
Universally composable two-party and multi-party secure computation
Approximating connectivity domination in weighted bounded-genus graphs
Further Algorithmic Aspects of the Local Lemma
3-manifold knot genus is NP-complet
Homomorphisms are a good basis for counting small subgraphs
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
Sorting in linear time?
Canonical form for graphs in quasipolynomial time: preliminary report
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract)
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA
Testing k-wise and almost k-wise independence
Graph Problems on a Mesh-Connected Processor Array (Preliminary Version)
Parameter-Passing Mechanisms and Nondeterminism
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
All non-trivial variants of 3-LDT are equivalent
Merge-Width and First-Order Model Checking
Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
On the Average Behavior of Set Merging Algorithms (Extended Abstract)
Routing permutations on graphs via matchings
Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
Folded codes from function field towers and improved optimal rate list decoding
A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Separating monotone VP and VNP
Monotone expansion
Algebraic approach to promise constraint satisfaction
A randomized linear-time algorithm for finding minimum spanning trees
Unexpected hardness results for Kolmogorov complexity under uniform reductions
The PL Hierarchy Collapses
Extractors for Samplable Distributions with Low Min-Entropy
Stronger calibration lower bounds via sidestepping
Implicit Data Structures (Preliminary Draft)
On data structures and asymmetric communication complexity
Optimal parallel suffix tree construction
Query complexity of approximate nash equilibria
Noise-Tolerant Distribution-Free Learning of General Geometric Concepts
Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
On derandomizing algorithms that err extremely rarely
Improved bounds on weak epsilon-nets for convex sets
A Partial Solution to the Reachability-Problem for Vector-Addition Systems
On a Multidimensional Search Problem (Preliminary Version)
Tight lower bounds for greedy routing in uniform small world rings
Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Competitive contagion in networks
Graph and map isomorphism and all polyhedral embeddings in linear time
How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
Quantifier Elimination in the Theory of an Algebraically-closed Field
Cell-probe lower bounds for dynamic problems via a new communication model
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
On Hiding Information from an Oracle (Extended Abstract)
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
Polynomial Algorithms for Linear Programming over the Algebraic Numbers
Lifting Markov Chains to Speed up Mixing
Bandits with switching costs: T 2/3 regret
Optimal Code Generation for Expression Trees
Second-Order Mathematical Theory of Computation
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences
Parallel repetition for all 3-player games over binary alphabet
A Programming Language Theorem Which Is Independent of Peano Arithmetic
Incremental Clustering and Dynamic Information Retrieval
Data-Dependent LSH for the Earth Mover's Distance
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
LALR(k) Testing is PSPACE-Complete
Randomized query processing in robot path planning (Extended Abstract)
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
On the integrality ratio of semidefinite relaxations of MAX CUT
Universal SNARGs for NP from Proofs of Correctness
Scheduling Data Transfers in a Network and the Set Scheduling Problem
Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
Dynamic suffix array with polylogarithmic queries and updates
Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability
Classical interaction cannot replace a quantum message
Approximation schemes for clustering problems
Some Results Concerning Efficient and Optimal Algorithms
String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
On achieving the "best of both worlds" in secure multiparty computation
Graph isomorphism in quasipolynomial time [extended abstract]
Proof of the Density Threshold Conjecture for Pinwheel Scheduling
An Area-Maximum Edge Length Tradeoff for VLSI Layout
Random sampling in residual graphs
Constant approximation for k-median and k-means with outliers via iterative rounding
Reproducibility in learning
Navigating in Unfamiliar Geometric Terrain (Preliminary Version)
Optimal static range reporting in one dimension
Size space tradeoffs for resolution
Subexponential Parameterized Algorithms for Hitting Subgraphs
The Complexity of Propositional Linear Temporal Logics
Provably Good Routing in Graphs: Regular Arrays
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
A discriminative framework for clustering via similarity functions
Optimal Load-Balanced Scalable Distributed Agreement
The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract)
Optimal Implementation of Conjunctive Queries in Relational Data Bases
The Realization of Monotone Boolean Functions (Preliminary Version)
Beating randomized response on incoherent matrices
Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract)
Polling: A New Randomized Sampling Technique for Computational Geometry
Clustering mixtures with almost optimal separation in polynomial time
Edge-Disjoint Paths in Eulerian Digraphs
Local Correction of Linear Functions over the Boolean Cube
Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract)
On the complexity of negation-limited Boolean networks
On the hardness of dominant strategy mechanism design
Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines
Computing correlated equilibria in multi-player games
Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap
Multiple matching of rectangular patterns
How to use expert advice
Threshold Functions and Bounded Depth Monotone Circuits
Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract)
Testing and Learning Structured Quantum Hamiltonians
Linear time encodable and list decodable codes
Going after the k-SAT threshold
Separating subadditive euclidean functionals
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Some perspective on computational complexity (abstract)
Clustering to minimize the sum of cluster diameters
On the learnability of discrete distributions
Survivable network design with degree or order constraints
Algorithms for dynamic geometric problems over data streams
Statistical algorithms and a lower bound for detecting planted cliques
Hard examples for bounded depth frege
Reducing isotropy and volume to KLS: an o *( n 3 ψ 2 ) volume algorithm
Towards asymptotic optimality in probabilistic packet marking
Geometric complexity theory and tensor rank
Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees (Correction)
New lattice based cryptographic constructions
Constant rank bimatrix games are PPAD-hard
Applications of approximation algorithms to cooperative games
An efficient algorithm for partial order production
A weight-size trade-off for circuits with MOD m gates
On codes decoding a constant fraction of errors on the BSC
Fast-converging tatonnement algorithms for one-time and ongoing market problems
An axiomatic approach to algebrization
New and improved constructions of non-malleable cryptographic protocols
Universal Classes of Hash Functions (Extended Abstract)
Efficient empirical revenue maximization in single-parameter auction environments
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Optimal error rates for interactive coding I: adaptivity and other settings
On the Theory of Programming Logics
On-line load balancing with applications to machine scheduling and virtual circuit routing
A Bound on the Multiplication Efficiency of Iteration
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
How to spread adversarial nodes?: rotate!
How to delegate computations: the power of no-signaling proofs
Small Universal Graphs
A simpler and faster strongly polynomial algorithm for generalized flow maximization
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
A combinatorial characterization of the testable graph properties: it's all about regularity
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
On the Learnability of Boolean Formulae
Deterministic Simulation of Non-Deterministic Turing Machines (Detailed Abstract)
Shallow Multiplication Circuits and Wise Financial Investments
Catching the k-NAESAT threshold
Short seed extractors against quantum storage
Phase Transitions via Complex Extensions of Markov Chains
Fast computation of low rank matrix
On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal
Chinese Remaindering with Errors
Evolvability from learning algorithms
Frozen 1-RSB structure of the symmetric Ising perceptron
Shielding circuits with groups
An impossibility result for truthful combinatorial auctions with submodular valuations
On the generation of multivariate polynomials which are hard to factor
A Complexity Theoretic Approach to Randomness
Can Finite Samples Detect Singularities of Real-Valued Functions?
Bit-probe lower bounds for succinct data structures
Sharp thresholds For monotone properties in random geometric graphs
A decentralized algorithm for spectral analysis
Tensor Concentration Inequalities: A Geometric Approach
Span programs for functions with constant-sized 1-certificates: extended abstract
A duality based unified approach to Bayesian mechanism design
Binary Search Trees of Bounded Balance
A Consistent and Complete Deductive System for the Verification of Parallel Programs
Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
Bounded degree cosystolic expanders of every dimension
Mixing time for the solid-on-solid model
Sub-constant error low degree test of almost-linear size
Towards optimal two-source extractors and Ramsey graphs
Dynamic TCP acknowledgement and other stories about e/(e-1)
Two Algorithms for Nearest-Neighbor Search in High Dimensions
Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract)
Pseudorandomness of ring-LWE for any ring and modulus
How Discreet is the Discrete Log?
Reliable Computation with Cellular Automata
Completeness Classes in Algebra
The log-approximate-rank conjecture is false
On adequate performance measures for paging
Prophet Inequalities with Cancellation Costs
A combinatorial construction of almost-ramanujan graphs using the zig-zag product
On Reductions and Representations of Learning Problems in Euclidean Spaces
On the Complexity of Protein Folding (Extended Abstract)
Explainable k -means: don't be greedy, plant bigger trees!
Hardness Condensation by Restriction
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract)
Uniform Closure Properties of P-Computable Functions
On Tape Versus Core; An Application of Space Efficient Perfect Hash Functions to the Invariance of Space
Consistency Thresholds for the Planted Bisection Model
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Graph sparsification by effective resistances
Complete Problems for Deterministic Polynomial Time
On the complexity of #CSP
A Flat Wall Theorem for Matching Minors in Bipartite Graphs
The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs
Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
Node Listings for Reducible Flow Graphs
Inverse conjecture for the gowers norm is false
Majority is stablest: discrete and SoS
Tight bounds for online vector bin packing
Decremental all-pairs shortest paths in deterministic near-linear time
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Borel Sets and Circuit Complexity
Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
Leveled Fully Homomorphic Signatures from Standard Lattices
Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)
Saving space by algebraization
On the Nisan-Ronen conjecture for submodular valuations
Multi-scale self-simulation: a technique for reconfiguring arrays with faults
How to Assemble Tree Machines (Extended Abstract)
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
Distributed computation in dynamic networks
A proof of the security of quantum key distribution (extended abstract)
Amortized Efficiency of List Update Rules
New trade-offs in cost-sharing mechanisms
A New Incompleteness Result for Hoare's System
Measuring Energy Consumption in VLSI Circuits: a Foundation
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Minimax option pricing meets black-scholes in the limit
A 5/4-Approximation for Two-Edge Connectivity
Verifying Partial Orders
Selfish traffic allocation for server farms
Universal Games of Incomplete Information
Algorithmic derandomization via complexity theory
Katyusha: the first direct acceleration of stochastic gradient methods
Optimal labelling schemes for adjacency, comparability, and reachability
Strong self-concordance and sampling
From Algebras to Programming Languages
A computational view of population genetics
Holant problems and counting CSP
A General Sequential Time-Space Tradeoff for Finding Unique Elements
Bounding delays in packet-routing networks
Secure multi-party quantum computation
Hardness amplification in proof complexity
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Cell-probe lower bounds from online communication complexity
Hypergraph Unreliability in Quasi-Polynomial Time
A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic
SNARGs under LWE via Propositional Proofs
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
On independent sets, 2-to-2 games, and Grassmann graphs
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound
Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers
Efficient Computation of Geodesic Shortest Paths
SDPs and Robust Satisfiability of Promise CSP
Near-optimal Quantum algorithms for multivariate mean estimation
Solving SDD linear systems in nearly m log 1/2 n time
Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing
Private stochastic convex optimization: optimal rates in linear time
Distributed Packet Switching in Arbitrary Networks
On the complexity of differentially private data release: efficient algorithms and hardness results
Improved approximation for node-disjoint paths in planar graphs
Coin flipping of any constant bias implies one-way functions
Upper and Lower Bounds on Time-Space Tradeoffs
A Unifying Framework for the Theory of Iterative Arrays of Machines
An NP-Complete Number-Theoretic Problem
Matroid prophet inequalities
Smoothing and cleaning up slivers
Coordinate Representation of Order Types Requires Exponential Storage
Disjoint Connected Dominating Sets in Pseudorandom Graphs
Psuedorandom Generators for Space-Bounded Computation
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
New Lower Bounds for Parallel Computation
Ideal Pseudorandom Codes
Linear Independence, Alternants, and Applications
An Optimal "It Ain't Over Till It's Over" Theorem
Mixture models, robustness, and sum of squares proofs
Natural proofs versus derandomization
The Swendsen-Wang Process Does Not Always Mix Rapidly
Submodular maximization with matroid and packing constraints in parallel
Computing with highly mixed states (extended abstract)
A Technique for Lower Bounding the Cover Time
Constructing a Perfect Matching is in Random NC
The complexity of constrained min-max optimization
Computability over Arbitrary Fields
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (Extended Abstract)
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence
Playing unique games on certified small-set expanders
Twenty (simple) questions
New Algorithms for All Pairs Approximate Shortest Paths
Semidefinite Programs Simulate Approximate Message Passing Robustly
Tensor norms and the classical communication complexity of nonlocal quantum measurement
Almost optimal super-constant-pass streaming lower bounds for reachability
Multiparty Unconditionally Secure Protocols (Extended Abstract)
Optimal competitive auctions
The power of localization for efficiently learning linear separators with noise
Elementary Bounds for Presburger Arithmetic
Faster min-plus product for monotone instances
A full characterization of quantum advice
Delegating computation: interactive proofs for muggles
Lower bounds for 2-dimensional range counting
Tradeoffs Between Communication and Space
The Consistency of "P = NP" and Related Problems with Fragments of Number Theory
Exact computations of the inertia symmetric integer matrices
Counting Linear Extensions is #P-Complete