yusuke1997/dblp-id-title huggingface dataset:
On the Parallel Computation of Local Operations
Balanced allocations: the heavily loaded case
Stronger bounds for weak epsilon-nets in higher dimensions
Low degree spanning trees of small weight
Coevolutionary opinion formation games
Randomized Speed-Ups in Parallel Computation
The PCP theorem by gap amplification
When is approximate counting for conjunctive queries tractable?
An O(n log n) Sorting Network
Complexity of counting CSP with complex weights
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Lower bounds on the amount of randomness in private computation
On the complexity of matrix product
Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract)
Linear Approximation of Shortest Superstrings
An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
Universal protocols for information dissemination using emergent signals
Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows
Beyond matroids: secretary problem and prophet inequality with general constraints
Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract)
A new proof of the weak pigeonhole principle
Explicit lower bounds via geometric complexity theory
On the Limits of Non-Approximability of Lattice Problems
On the computational power of depth 2 circuits with threshold and modulo gates
Clustering for edge-cost minimization (extended abstract)
Distributed approximation algorithms for weighted shortest paths
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Polynomial time deterministic identity testing algorithm for Σ [3] ΠΣΠ [2] circuits via Edelstein-Kelly type theorem for quadratic polynomials
The Correctness of a Modified SECD Machine
On the Complexity of Grammar and Related Problems
On the hardness of approximating minimization problems
A Delaunay based numerical method for three dimensions: generation, formulation, and partition
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
Construction of new local spectral high dimensional expanders
Deterministic mincut in almost-linear time
On the optimal time/space tradeoff for hash tables
The Complexity of Dynamic Languages and Dynamic Optimization Problems
Time-space tradeoffs for implementations of snapshots
A nearly optimal oracle for avoiding failed vertices and edges
Sample-efficient proper PAC learning with approximate differential privacy
Segmentation Problems
Computational Lower Bounds for No-Regret Learning in Normal-Form Games
Improved PIR Schemes using Matching Vectors and Derivatives
Communication lower bounds using directional derivatives
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada
Computability Concepts for Programming Language Semantics
Connectivity and inference problems for temporal networks
A fast and efficient algorithm for low-rank approximation of a matrix
Approximations and Optimal Geometric Divide-And-Conquer
Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)
The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement
An O~(n 2 ) algorithm for minimum cuts
Lower bounds for off-line range searching
Efficient Robust Parallel Computations (Extended Abstract)
Entangled simultaneity versus classical interactivity in communication complexity
Parallel Depth-First Search in General Directed Graphs (Preliminary Version)
Lattice Problems beyond Polynomial Time
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols
Approximate Distance Sensitivity Oracles in Subquadratic Space
Cell-probe lower bounds for the partial match problem
Moser and tardos meet Lovász
The round complexity of verifiable secret sharing and secure multicast
A Tight Analysis of the Greedy Algorithm for Set Cover
Matrix Chaos Inequalities and Chaos of Combinatorial Type
Conditional hardness of precedence constrained scheduling on identical machines
A Theorem on Probabilistic Constant Depth Computations
Linearizable implementations do not suffice for randomized distributed computation
Approximate counting and sampling via local central limit theorems
L p Row Sampling by Lewis Weights
Small Sets Supporting Fáry Embeddings of Planar Graphs
Fast Learning of k-Term DNF Formulas with Queries
Improved bounds on the max-flow min-cut ratio for multicommodity flows
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
On the Distribution of Independent Formulae of Number Theory
Storage Requirements for Deterministic Polynomial Time Recognizable Languages
An Improved Approximation Guarantee for Prize-Collecting TSP
Asynchronous secure computation
Computable Queries for Relational Data Bases (Preliminary Report)
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Approximating text-to-pattern Hamming distances
Efficient massively parallel methods for dynamic programming
Huffman coding with unequal letter costs
Key agreement from weak bit agreement
Near-optimal fully-dynamic graph connectivity
Two Steiner tree packing problems (Extended Abstract)
Evaluation May Be Easier Than Generation (Extended Abstract)
Rate one-third non-malleable codes
Dynamic Parallel Complexity of Computational Circuits
Counting small induced subgraphs with hereditary properties
An Algebraic System for Process Structuring and Interprocess Communication
A framework for quadratic form maximization over convex sets through nonconvex relaxations
Sharing the cost of muliticast transmissions (preliminary version)
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
One line and n points
Meet and merge: approximation algorithms for confluent flows
Robust satisfiability of constraint satisfaction problems
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Two prover protocols: low error at affordable rates
Page Replacement with Multi-Size Pages and Applications to Web Caching
Pseudorandom generators for polynomial threshold functions
Compositions of n Tree Transducers
Simulating access to hidden information while learning
A Difference in Efficiency between Synchronous and Asynchronous Systems
Universal O (Congestion + Dilation + log 1+epsilon N ) Local Control Packet Switching Algorithms
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Using Smoothness to Achieve Parallelism (Abstract)
A Comparison of Instruction Sets for Stack Machines
Counting Networks and Multi-Processor Coordination
Rounding sum-of-squares relaxations
Circuit complexity: from the worst case to the average case
Random walks on polytopes and an affine interior point method for linear programming
Near-optimal small-depth lower bounds for small distance connectivity
Quantum Spectrum Testing
Distribution functions of probabilistic automata
Locality-Preserving Hashing in Multidimensional Spaces
Test-and-Set in Optimal Space
A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)
Batch Proofs Are Statistically Hiding
New separations results for external information
Towards an optimal separation of space and length in resolution
Rounds in Communication Complexity Revisited
Translations on a Context Free Grammar
Faster energy maximization for faster maximum flow
The History and Status of the P versus NP Question
Efficiency Considerations in Using Semi-random Sources (Extended Abstract)
Strict fibonacci heaps
On the Additions Necessary to Compute Certain Functions
Data-dependent hashing via nonlinear spectral gaps
Entropic independence: optimal mixing of down-up random walks
Low distortion embeddings for edit distance
Improved approximation for directed cut problems
Primal-dual algorithms for deterministic inventory problems
A Theorem on Sensitivity and Applications in Private Computation
Unsolvability Considerations in Computational Complexity
Quantum bit escrow
3-query locally decodable codes of subexponential length
Additive approximation for bounded degree survivable network design
Learning Arithmetic Read-Once Formulas
Private Graphon Estimation via Sum-of-Squares
Near-perfect load balancing by randomized rounding
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract)
Private coresets
Economic efficiency requires interaction
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
Tatonnement beyond gross substitutes?: gradient descent to the rescue
Positive spectrahedra: invariance principles and pseudorandom generators
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
An O ( n log n )-Size Fault-Tolerant Sorting Network (Extended Abstract)
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Optimal Static Dictionary with Worst-Case Constant Query Time
Private PAC learning implies finite Littlestone dimension
Pseudo-Random Generators under Uniform Assumptions
Search for the maximum of a random walk
Fast, Robust Approximate Message Passing
Output-Sensitive Approximate Counting via a Measure-Bounded Hyperedge Oracle, or: How Asymmetry Helps Estimate k-Clique Counts Faster
Product Mixing in Compact Lie Groups
Addressable Data Graphs: Extended Abstract
Ray Shooting and Parametric Search
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Optimal Disk I/O with Parallel Block Transfer (Extended Abstract)
Consistent load balancing via spread minimization
Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs
Outcome indistinguishability
Fourier PCA and robust tensor decomposition
Tradeoffs for VLSI Models with Subpolynomial Delay
Log-concave polynomials in theory and applications (tutorial)
Improved approximations of packing and covering problems
Time-space hardness of learning sparse parities
Time optimal self-stabilizing synchronization
Probabilistic Recurrence Relations
Almost optimal permutation routing on hypercubes
A unifying method for the design of algorithms canonizing combinatorial objects
Holographic algorithms: from art to science
Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract)
An approximate König's theorem for edge-coloring weighted bipartite graphs
Lower bounds for RAMs and quantifier elimination
Oracle separation of BQP and PH
Online trading algorithms and robust option pricing
Beating 1-1/e for ordered prophets
Iteration Theorems for LL(k) Languages
Near optimal multiple alignment within a band in polynomial time
On the importance of idempotence
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Reconstruction of depth-4 multilinear circuits with top fan-in 2
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling
Reed-Muller codes achieve capacity on erasure channels
Some Results in Tree Automata
Quantum lower bound for the collision problem
Polylogarithmic approximation for Euler genus on bounded degree graphs
Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
Counting curves and their projections
Complete characterization of security notions for probabilistic private-key encryption
All-pairs bottleneck paths for general graphs in truly sub-cubic time
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Counting hypergraph colourings in the local lemma regime
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Non-black-box simulation in the fully concurrent setting
Depth reduction for noncommutative arithmetic circuits
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance
A Representation for Linear Lists with Movable Fingers
Witness Indistinguishable and Witness Hiding Protocols
Flow time scheduling with uncertain processing time
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)
Infeasibility of instance compression and succinct PCPs for NP
Error-Correction of Matrix Multiplication Algorithms
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Automating algebraic proof systems is NP-hard
Riemann's Hypothesis and Tests for Primality
A Logarithmic Time Sort for Linear Size Networks
Sample Spaces Uniform on Neighborhoods
Approximation algorithms for combinatorial auctions with complement-free bidders
Succinct blind Quantum computation using a random oracle
The price of selfish routing
On non-uniform multicommodity buy-at-bulk network design
Real stable polynomials and matroids: optimization and counting
Optimal mechanism design and money burning
Efficient probabilistically checkable proofs and applications to approximations
Symmetric Complementation
How robust are linear sketches to adaptive inputs?
Additive versus exponentiated gradient updates for linear prediction
A new protocol and lower bounds for quantum coin flipping
Inapproximability of the Tutte polynomial
Search via quantum walk
Algorithmic Pirogov-Sinai theory
Parallel randomized load balancing (Preliminary Version)
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Transition Logic: How to Reason About Temporal Properties in a Compositional Way
Efficiently learning structured distributions from untrusted batches
Planar graphs of bounded degree have bounded queue number
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge
Neighborhood Search Algorithms for Finding Optimal Traveling Salesman Tours Must Be Inefficient
Understanding the Cluster Linear Program for Correlation Clustering
Pseudorandom generators for low degree polynomials
Lower Bounds for Regular Resolution over Parities
Minimum Degree Edge-Disjoint Hamilton Cycles in Random Directed Graphs
Interactive channel capacity
Statistically-hiding commitment from any one-way function
Sum-of-Squares Lower Bounds for Densest k-Subgraph
The Computation of Finite Functions
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA
Validating Register Allocations for Straight Line Programs
Nearly-linear size holographic proofs
Aspects of Information Flow in VLSI Circuits (Extended Abstract)
Propositional Dynamic Logic of Looping and Converse
Relations between average case complexity and approximation complexity
Smoothed analysis of tensor decompositions
Deterministic distributed edge-coloring with fewer colors
Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
Hierarchies for semantic classes
Finding a Small Vertex Cut on Distributed Networks
Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal
The fourier transform of poisson multinomial distributions and its algorithmic applications
Self-Adjusting Binary Trees
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Almost tight bounds for reordering buffer management
Sampling lower bounds via information theory
An efficient parallel repetition theorem for Arthur-Merlin games
How many queries are needed to learn?
Almost-Optimal Sublinear Additive Spanners
Motion planning for a steering-constrained robot through moderate obstacles
Program Size and Economy of Descriptions: Preliminary Report
A Theory of the Learnable
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
On the (Combinatorial) Structure of L Languages without Interactions
Isomorphism of Graphs with Bounded Eigenvalue Multiplicity
Limits to list decoding Reed-Solomon codes
Constant Query Local Decoding against Deletions Is Impossible
Faster approximate lossy generalized flow via interior point algorithms
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
Quantum Advantage from Any Non-local Game
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
Are many small sets explicitly small?
A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
Examples of Hard Tautologies in the Propositional Calculus
Exponential algorithmic speedup by a quantum walk
Abstract Families of Processors
Almost Optimal Lower Bounds for Small Depth Circuits
Adaptive Zero Knowledge and Computational Equivocation (Extended Abstract)
Adaptive Packet Routing for Bursty Adversarial Traffic
Universal approximations for TSP, Steiner tree, and set cover
Approximation Guarantees of Median Mechanism in ℝᵈ
Adaptive versus Nonadaptive Attribute-Efficient Learning
Are Search and Decision Problems Computationally Equivalent?
No-Regret Learning in Bilateral Trade via Global Budget Balance
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Approximate polymorphisms
The risk profile problem for stock portfolio optimization (extended abstract)
Improvements in throughout maximization for real-time scheduling
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals
Smoothed complexity of local max-cut and binary max-CSP
Analysis of Structured Programs
Breaking the k 2 barrier for explicit RIP matrices
a Combinatorial Problem which is Complete in Polynomial Space
Pricing ordered items
Optimal inapproximability of satisfiable k-LIN over non-abelian groups
Oblivious dimension reduction for k -means: beyond subspaces and the Johnson-Lindenstrauss lemma
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
Finding Almost-Satisfying Assignments
Non-Expansive Hashing
Protecting Data Privacy in Private Information Retrieval Schemes
The Parallel Complexity of Exponentiating Polynomials over Finite Fields
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract)
Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors
Extractor-based time-space lower bounds for learning
Supercritical Tradeoffs for Monotone Circuits
Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks
On Non-linear Lower Bounds in Computational Complexity
Proving Assertions about Programs that Manipulate Data Structures
Revisiting Local Computation of PageRank: Simple and Optimal
Piecewise linear paths among convex obstacles
Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing
The Macro Model for Data Compression (Extended Abstract)
1+ ε approximation of tree edit distance in quadratic time
Attribute-based encryption for circuits
Connection Caching
Simple and efficient leader election in the full information model
Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets
On omega-Automata and Temporal Logic (Preliminary Report)
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Near-optimal learning of tree-structured distributions by Chow-Liu
The Boolean Formula Value Problem Is in ALOGTIME
The computational complexity of ball permutations
New notions of security: achieving universal composability without trusted setup
A quasi-PTAS for unsplittable flow on line graphs
Quantum de finetti theorems under local measurements with applications
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
Formula lower bounds via the quantum method
Algorithms for Routing and Testing Routability of Planar VLSI Layouts
Capacity lower bounds via productization
Optimal error resilience of adaptive message exchange
A proof of Alon's second eigenvalue conjecture
Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier
The minimum latency problem
Multiplying matrices faster than coppersmith-winograd
A stochastic process on the hypercube with applications to peer-to-peer networks
Quantum and Classical Query Complexities of Functions of Matrices
An optimal ancestry scheme and small universal posets
An almost-optimally fair three-party coin-flipping protocol
The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories)
Shellability Is Hard Even for Balls
Combinatorial Optimization with Rational Objective Functions
Online bipartite matching with unknown distributions
Generalization and equilibrium in generative adversarial nets (GANs) (invited talk)
Detection is Easier than Computation (Extended Abstract)
Quantum proof systems for iterated exponential time, and beyond
Private approximation of search problems
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Every 2-CSP allows nontrivial approximation
Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Solving Dense Linear Systems Faster Than via Preconditioning
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
Athena lecture: Controlling Access to Programs?
Uniformly Erasable AFL
Undirected ST-connectivity in log-space
A lower bound for the distributed Lovász local lemma
Testing unateness nearly optimally
New hardness results for routing on disjoint paths
Symmetric logspace is closed under complement
Online matching with concave returns
Fast Computation Using Faulty Hypercubes (Extended Abstract)
Redundancy Is All You Need
Modular Competitiveness for Distributed Algorithms
A theory of universal learning
Visibly pushdown languages
Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012
Fast polynomial factorization and modular composition in small characteristic
Intrinsic robustness of the price of anarchy
The difficulty of testing for isomorphism against a graph that is given in advance
Witness-Based Cryptographic Program Checking and Robust Function Sharing
Approximating Nash Social Welfare by Matching and Local Search
Round compression for parallel matching algorithms
An Improved Approximation Algorithm for Multiway Cut
Efficient 3-D Range Searching in External Memory
Properties of Deterministic Top Down Grammars
On the Time and Tape Complexity of Languages I
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract)
Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract)
On Aspects of Universality and Performance for Closed Hashing (Extended Abstract)
Distance sensitivity oracles with subcubic preprocessing time and fast query time
Improved algorithms for submodular function minimization and submodular flow
The Degree Hierarchy of Undecidable Problems of Formal Grammars
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Calibrated Language Models Must Hallucinate
Learning Quantum States Prepared by Shallow Circuits in Polynomial Time
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA
A quasi-polynomial time approximation scheme for minimum weight triangulation
Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates
Speedups of Deterministic Machines by Synchronous Parallel Machines
Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
A Linear Probing Sort and its Analysis (Preliminary Draft)
Fast quantum algorithms for computing the unit group and class group of a number field
A New Information Complexity Measure for Multi-pass Streaming with Applications