yusuke1997/dblp-id-title huggingface dataset:
Parallel Graph Connectivity in Log Diameter Rounds
Dynamic deadlock resolution protocols (Extended Abstract)
Dynamic Networks Are as Fast as Static Networks (Preliminary Version)
Streaming Facility Location in High Dimension via Geometric Hashing
On Depth-Reduction and Grates
Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games
31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I
Satisfiability of Word Equations with Constants is in Exponential Space
The Cost of Cache-Oblivious Searching
An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion
Linear Lower Bounds on Real-World Implementations of Concurrent Objects
Full AFLs and Nested Iterated Substitution
The Resolution of a Hartmanis Conjecture
Structural Simplification and Decomposition of Asynchronous Sequential Circuits
Online Node-Weighted Steiner Forest and Extensions via Disk Paintings
Approximation Algorithms for Noncommutative CSPs
A New Efficient Radix Sort
Crossing sequences and off-line Turing machine computations
Decidability of Non-interactive Simulation of Joint Distributions
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
Tight Time-Space Lower Bounds for Constant-Pass Learning
Efficient Minimum Cost Matching Using Quadrangle Inequality
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms
Concurrency Control for Database Systems
On Lifted Problems (Preliminary Reports)
Solving Optimization Problems with Diseconomies of Scale via Decoupling
Load Balancing and Density Dependent Jump Markov Processes (extended abstract)
On Computational Speed-Up
Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract)
An Improved Algorithm for Quantifier Elimination Over Real Closed Fields
The Recognition Problem for the Set of Perfect Squares
Some Observations on the Average Behavior of Heapsort (Preliminary Report)
An Improvement of Valiant's Decision Procedure for Equivalence of Deterministic Finite-Turn Pushdown Automata
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
Exponential quantum speedup in simulating coupled classical oscillators *
Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time
Exponentially Faster Massively Parallel Maximal Matching
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums
Replacement Paths via Fast Matrix Multiplication
Refuting Smoothed 3CNF Formulas
Factoring Graphs to Bound Mixing Rates
Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
All Pairs Almost Shortest Paths
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
Predicting {0,1}-Functions on Randomly Drawn Points (Extended Abstract)
Min-max Graph Partitioning and Small Set Expansion
Loop Elimination and Loop Reduction-A Model-Theoretic Analysis of Programs (Partial Report)
Punctured Low-Bias Codes Behave Like Random Linear Codes
A Proof of the Kahn-Kalai Conjecture
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
Property Testing and Its Connection to Learning and Approximation
Area-Optimal Three-Layer Channel Routing
Information Theoretic Reductions among Disclosure Problems
Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version)
An optimal algorithm for the All-Nearest-Neighbors Problem
Equivalences and Transformations of Recursive Definitions
Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs
Optimal Prefetching via Data Compression (Extended Abstract)
Hardness Magnification for Natural Problems
Ideas on asynchronous feedback networks
Compressing Interactive Communication under Product Distributions
Complexity of Unification in Free Groups and Free Semi-groups
Optimal Tradeoffs for Estimating Pauli Observables
Planar Reachability in Linear Space and Constant Time
Unbounded Program Memory Adds to the Expressive Power of First-Order Dynamic Logic (Extended Abstract)
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates
On-Line Simulation of k+1 Tapes by k Tapes Requires Nonlinear Time
Online Algorithms for Finger Searching (Extended Abstract)
Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
Randomized Rumor Spreading
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
Testing Low-Degree Polynomials over Prime Fields
Settling the APX-Hardness Status for Geometric Set Cover
Undirected Single Source Shortest Path in Linear Time
Improved Upper Bounds on Shellsort
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution
Structural Equivalence of Context-Free Grammars
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency
Derandomizing Semidefinite Programming Based Approximation Algorithms
A New Minimax Theorem for Randomized Algorithms (Extended Abstract)
Truth functions realizable by single threshold organs
Locking Policies: Safety and Freedom from Deadlock
Learning in Pessiland via Inductive Inference
Replicability in High Dimensional Statistics
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Investigation and simulation of a self-repairing digital computer
The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time
Cost-Distance: Two Metric Network Design
Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
New upper bounds in Klee's measure problem (extended abstract)
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment
Scale-sensitive Dimensions, Uniform Convergence, and Learnability
The Program Complexity of Searching a Table
Selection and Sorting with Limited Storage
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Laconic Function Evaluation and Applications
Isomorphism Testing for Graphs of Bounded Rank Width
The Complexity of Factors of Multivariate Polynomials
Designing Systolic Algorithms Using Sequential Machines
The Simple Economics of Approximately Optimal Auctions
A Permanent Approach to the Traveling Salesman Problem
Finding Near Optimal Separators in Planar Graphs
Some Polynomial and Integer Divisibility Problems Are NP-Hard
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D
Beyond VCG: Frugality of Truthful Mechanisms
On the Computation Time of Finite Functions
No Small Linear Program Approximates Vertex Cover within a Factor 2 - e
Approximate Strip Packing
Global Decision Problems for Relational Databases
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
GO Is PSPACE Hard
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
Efficient Construction of Rigid Matrices Using an NP Oracle
Universal Packet Routing Algorithms (Extended Abstract)
Algebraic Decision Trees and Euler Characteristics
Deterministic Fully Dynamic SSSP and More
Finding Disjoint Paths in Expanders Deterministically and Online
On Parallelism in Turing Machines
Ramanujan Complexes and Bounded Degree Topological Expanders
Programmed Grammars: A New Device for Generating Formal Languages
The Complexity of Approximating Vertex Expansion
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
Mechanism Design with Set-Theoretic Beliefs
Proofs by Induction in Equational Theories with Constructors
Privacy Amplification and Non-malleable Extractors via Character Sums
On Star-Free Events
IP over connection-oriented networks and distributional paging
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
On Finding and Updating Shortest Paths and Spanning Trees
Covering Problems with Hard Capacities
Approximate Checking of Polynomials and Functional Equations (extended abstract)
On the Knowledge Complexity of NP
Pandora's Box with Correlations: Learning and Approximation
Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
Functional Decomposition of Polynomials
An Adaptive Step Toward the Multiphase Conjecture
On the Limits to Speed Up Parallel Machines by Large Hardware and Unbounded Communication
Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract)
A Theoretical Framework for Memory-Adaptive Algorithms
Speed is as Powerful as Clairvoyance
Nondeterministic versus Probabilistic Linear Search Algorithms
A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract)
Fault Tolerant Data Structures
Memory-Span Concepts and the Synthesis of Sequential Machines in Feedback Shift-Register Form
Hardness of Approximating Sigma 2 p Minimization Problems
Testing linear-invariant properties
The Hardness of 3 - Uniform Hypergraph Coloring
Grammars with Linear Time Functions
Meshes with Multiple Buses
The Complexity of Parallel Comparison Merging
Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
Improved Smoothed Analysis of the Shadow Vertex Simplex Method
Disjoint Paths in Densely Embedded Graphs
Testing for Concise Representations
Near-linear Size Hypergraph Cut Sparsifiers
A Non-linear Time Lower Bound for Boolean Branching Programs
Points on Computable Curves
Parallel Comparison Algorithms for Approximation Problems
On Obstructions in Relation to a Fixed Viewpoint
Pseudorandom Generators, Measure Theory, and Natural Proofs
On Distinguishing Prime Numbers from Composite Numbers (Abstract)
A Time-Space Tradeoff for Boolean Matrix Multiplication
Storage Management for Evolving Databases
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
Truly Online Paging with Locality of Reference
Source Routing and Scheduling in Packet Networks
Semirandom Planted Clique and the Restricted Isometry Property
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges
Fishspear: A Priority Queue Algorithm (Extended Abstract)
Determinant Sums for Undirected Hamiltonicity
Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms
Testing Subgraphs in Large Graphs
An Application of Simultaneous Approximation in Combinatorial Optimization
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
On Lower Bounds for Computing the i-th Largest Element
A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time
Lower Bounds for the Noisy Broadcast Problem
Affine Extractors for Almost Logarithmic Entropy
Distribution of the threshold for the symmetric perceptron
Adaptive Dictionary Matching
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure
Fourier Growth of Communication Protocols for XOR Functions
Amortized Communication Complexity (Preliminary Version)
Dynamic Three-Dimensional Linear Programming
Non-Interactive CryptoComputing For NC 1
On the Applications of Multiplicity Automata in Learning
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
Minimal Boolean expressions with more than two levels of sums and products
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, 2009
On the Implementation of Huge Random Objects
Refinements of the Nondeterministic Time and Space Hierarchies
A Randomized Approximation Scheme for Metric MAX-CUT
LDPC Codes Achieve List Decoding Capacity
Decoding Quasi-Cyclic Quantum LDPC Codes
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time
Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits
Approximation of Diameters: Randomization Doesn't Help
Geometric Separator Theorems & Applications
Substitution of Bounded Rational Cone
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
On the AC0 Complexity of Subgraph Isomorphism
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
Learning Polynomials with Queries: The Highly Noisy Case
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
Directed vs. Undirected Monotone Contact Networks for Threshold Functions
The Power of Linear Programming for Valued CSPs
Some Results in Computational Topology
Apple Tasting and Nearly One-Sided Learning
The Temporal Logic of Programs
Boolean two-terminal analysis and synthesis
Quantum Tanner codes
Size Bounds and Query Plans for Relational Joins
A Second Step toward the Polynomial Hierarchy
Paths, Trees, and Minimum Latency Tours
Leakage-Resilient Cryptography
k+1 Heads Are Better than k for PDA's
How to Play Unique Games Using Embeddings
Round Complexity of Authenticated Broadcast with a Dishonest Majority
Hardness of Approximating the Shortest Vector Problem in Lattices
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
Universal Stability Results for Greedy Contention-Resolution Protocols
On the Bit Extraction Problem
Recursive *-Tree Parallel Data-Structure (Extended Abstract)
Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
1st Annual Symposium on Switching Circuit Theory and Logical Design, Chicago, Illinois, USA, October 9-14, 1960
Indexed Grammars-An Extension of Context Free Grammars
Cryptography In the Bounded Quantum-Storage Model
Network Extractor Protocols
Computational Transition at the Uniqueness Threshold
Constructing Non-malleable Commitments: A Black-Box Approach
Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version)
Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract)
A diagrammatic approach to multi-level logic synthesis
An Application of Number Theory to the Organization of Raster-Graphics Memory (Extended Abstract)
On Time versus Space II
Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
An Algorithm for Constructing the Aspect Graph
A Theory of Competitive Analysis for Distributed Algorithms
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems
A New Infinity of Distance Oracles for Sparse Graphs
Computing Approximate Centerpoints in Polynomial Time
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Hardness of Learning Halfspaces with Noise
Lower Bounds for Zero Knowledge on the Internet
On Triangulations of a Set of Points in the Plane
Determining Edge Connectivity in O(nm)
Every decision tree has an in.uential variable
Adjacency Labelling for Planar Graphs (and Beyond)
k-Means Has Polynomial Smoothed Complexity
A Characterization of Probabilistic Inference
On the Power of One-Way Communication
The Unbounded-Error Communication Complexity of Symmetric Functions
Effective Computability in Algebraic Structures (A Schematology Approach)
Lupanov Decoding Networks
The Application of Threshold Logic to the Design of Sequential Machines
Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs
Modular Decomposition of Synchronous Sequential Machines
Cut Query Algorithms with Star Contraction
Holiac-A family of student-constructed logic teaching aids
Optimal Dynamic Interval Management in External Memory (extended abstract)
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
A reduction technique for prime implicant tables
Efficient Sketches for Earth-Mover Distance, with Applications
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time
What search algorithm gives optimal average-case performance when search resources are highly limited?
Preventing False Discovery in Interactive Data Analysis Is Hard
Geometric Applications of Davenport-Schinzel Sequences
Lower Bounds for Algebraic Computation Trees with Integer Inputs
Agreement Testing Theorems on Layered Set Systems
The Ising Partition Function: Zeros and Deterministic Approximation
Multiple-Person Alternation
Locally Testable Codes and PCPs of Almost-Linear Length
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
Operations of finite automata
Non-Preemptive Min-Sum Scheduling with Resource Augmentation
Complexity classes in communication complexity theory (preliminary version)
Speeding up Dynamic Programming
Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes
Translational methods and computational complexity
Quantum Lower Bounds by Polynomials
Learning Sums of Independent Integer Random Variables
Straighting Polygonal Arcs and Convexifying Polygonal Cycles
Multiple-Input Change Asynchronous Machines Using Controlled Excitation and Flip-Flops
Tight Approximation Results for General Covering Integer Programs
The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)
Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem
Multiplication Is the Easiest Nontrivial Arithmetic Function
Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis
Medium Access Using Queues
Communication Complexity Towards Lower Bounds on Circuit Depth
A Nearly-m log n Time Solver for SDD Linear Systems
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]
Randomized Multidimensional Search Trees: Further Results in Dynamic Sampling (Extended Abstract)
On Similarity and Duality of Computation (Extended Abstract)
Identification Is Easier Than Decoding
An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract)
On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates
Theoretical Issues in Probabilistic Artificial Intelligence
Obstructions to Erdös-Pósa Dualities for Minors
Efficient Approximate Unitary Designs from Random Pauli Rotations
Approximation Schemes for Constrained Scheduling Problems
Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity
Digital Morphogenesis via Schelling Segregation
The Cube-Connected-Cycles: A Versatile Network for Parallel Computation (Extended Abstract)
Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)
Derandomizing Arthur-Merlin Games Using Hitting Sets
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut
On Multiple Input Change Hazard-Free Combinatorial Switching Circuits without Feedback
The Hardness of Metric Labeling
On the Power of Randomization in Algorithmic Mechanism Design
On the Single-Source Unsplittable Flow Problem
On the Hartmanis-Stearns Problem for a Class of TAG Machines
An Invariance Principle for the Multi-slice, with Applications
Pure-Circuit: Strong Inapproximability for PPAD
Strong Backdoors to Bounded Treewidth SAT
The Complexity of Renaming
Implicit B-Trees: New Results for the Dictionary Problem
Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions
Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps
Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method
How to Denest Ramanujan's Nested Radicals
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended abstract)
Minimizing Average Flow-time: Upper and Lower Bounds
47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings
Efficient Certificates of Anti-Concentration Beyond Gaussians
Group isomorphism is nearly-linear time for most orders
Testing Positive Semi-Definiteness via Random Submatrices
Why and How to Establish a Private Code on a Public Network (Extended Abstract)
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs
The Parallel Complexity of the Subgraph Connectivity Problem
Improved Bounds and Algorithms for Hypergraph Two-Coloring
Lower Bounds on the Efficiency of Generic Cryptographic Constructions
Two-Type Bracketed Grammars
Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs
On the Complexity of omega-Automata
Extended Precedence Languages, Bounded Right Context Languages, and Deterministic Languages (Extended Abstract)
An Improved Quantum Fourier Transform Algorithm and Applications
More about threshold logic
Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
Online Buy-at-Bulk Network Design
Syntax Directed Mappings of Context-Free Languages
On the Computational Complexity of Coin Flipping
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
Abstract Families of Languages
Optimal Interactive Coding for Insertions, Deletions, and Substitutions
Extracting Randomness Using Few Independent Sources
Optimal Parallel All-Nearest-Neighbors Using the Well-Separated Pair Decomposition (Preliminary Version)
The Cutting Plane Method Is Polynomial for Perfect Matchings
Simple Constructions of Almost k-Wise Independent Random Variables
Characterization of Context-Free Grammatical Families
Barriers to Near-Optimal Equilibria
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Single Pass Spectral Sparsification in Dynamic Streams
Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Probabilities of Sentences about Very Sparse Random Graphs
Fully Dynamic Maximal Matching in O (log n) Update Time
Beyond Competitive Analysis
Succinct Certificates for the Solvability of Binary Quadratic Diophantine Equations
Noise Sensitivity on the p -Biased Hypercube
Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications)
Computing Sums of Radicals in Polynomial Time
Approximating Shortest Superstrings
Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version)
On the Computational Power of Sigmoid versus Boolean Threshold Circuits
Agnostic Estimation of Mean and Covariance
Safraless Decision Procedures
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer
On the Effects of Feedback in Dynamic Network Protocols (Preliminary Version)
Faster Uniquely Represented Dictionaries
Spherical Cubes and Rounding in High Dimensions
Approximate Graph Coloring by Semidefinite Programming
The Weighted Majority Algorithm
Local List Recovery of High-Rate Tensor Codes & Applications
Linear Waste of Best Fit Bin Packing on Skewed Distributions
Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body