yusuke1997/dblp-id-title huggingface dataset:
The Average-Case Complexity of Determining the Majority
Answering n 2+o(1) Counting Queries with Differential Privacy is Hard
A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
Listing All Minimal Separators of a Graph
An Analysis of a Good Algorithm for the Subtree Problem
Analysis of Early-Insertion Standard Coalesced Hashing
Gadgets, Approximation, and Linear Programming
Strengths and Weaknesses of Quantum Computing
An Online Algorithm for Improving Performance in Navigation
Freedom from Deadlock of Safe Locking Policies
On Multirate Rearrangeable Clos Networks
Learning Decision Trees Using the Fourier Spectrum
On-Line Bin Packing of Items of Random Sizes, II
Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2)
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
An Extension of Liouville's Theorem on Integration in Finite Terms
Lower Bounds for (MOD p -MOD m ) Circuits
The Bit Complexity of Randomized Leader Election on a Ring
A Generalized Asymptotic Upper Bound on Fast Polynomial Evaluation and Interpolation
Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
On Approximately Counting Colorings of Small Degree Graphs
Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
Approximate Polytope Membership Queries
Recursion Structure Simplification
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
The Computing Time of the Euclidean Algorithm
On the Power of Conditional Samples in Distribution Testing
Rapid Multiplication of Rectangular Matrices
The NP-Completeness of Edge-Coloring
Whether a Set of Multivalued Dependencies Implies a Join Dependency is NP-Hard
On the Decomposability of NC and AC
Every Prime has a Succinct Certificate
A Method of Constructing Selection Networks with O(log n) Depth
Min-Max Graph Partitioning and Small Set Expansion
Self-Organizing Heuristics for Implicit Data Structures
Speed Scaling for Weighted Flow Time
On String Pattern Matching: A New Model with a Polynomial Time Algorithm
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
A Linear Recognition Algorithm for Cographs
Solution of a Divide-and-Conquer Maximin Recurrence
Learning Simple Concept Under Simple Distributions
Partial and Total Matrix Multiplication
The Sign-Rank of AC 0
On Bipartite Drawings and the Linear Arrangement Problem
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
Multidimensional Searching Problems
Using Petal-Decompositions to Build a Low Stretch Spanning Tree
Restructuring Partitioned Normal Form Relations without Information Loss
Improved Algorithms for Bipartite Network Flow
Is the Interesting Part of Process Logic Uninteresting? A Translation from PL to PDL
Efficient Parallel Algorithms for String Editing and Related Problems
Blocking Small Cuts in a Network, and Related Problems
Compatible Orderings on the Metric Theory of Trees
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
Tightening Nonsimple Paths and Cycles on Surfaces
On "Axiomatising Finite Concurrent Processes"
Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Finding All Spanning Trees of Directed and Undirected Graphs
Cutting Corners Cheaply, or How to Remove Steiner Points
Approximating the Longest Cycle Problem in Sparse Graphs
A New Approach to Stable Matching Problems
Pseudo-Line Arrangements: Duality, Algorithms, and Applications
Proof Complexity and the Binary Encoding of Combinatorial Principles
Erratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel Matrices
A New Representation of the Rational Numbers for Fast Easy Arithmetic
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
On Finding and Verifying Locally Optimal Solutions
An Efficient Method for Weighted Sampling Without Replacement
Derivation of Confidence Intervals for Work Rate Estimators in a Closed Queuing Network
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
A New Algorithm for Finding all Shortest Paths in a Graph of Positive Arcs in Average Time 0(n 2 log 2 n)
Universal Limit Laws for Depths in Random Trees
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
Minimum Cuts for Circular-Arc Graphs
Bounding the Power of Preemption in Randomized Scheduling
Inverting Polynomials and Formal Power Series
Envy-Free Makespan Approximation
Average Time Analysis of Clause Order Backtracking
Finding Separator Cuts in Planar Graphs within Twice the Optimal
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
On the Parallel Evaluation of Boolean Expressions
Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm
Linear Independence, Alternants and Applications
The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
The Computational Power of Depth Five Arithmetic Circuits
The Approximation Ratio of the k -Opt Heuristic for the Euclidean Traveling Salesman Problem
New Results on Monotone Dualization and Generating Hypergraph Transversals
An Analysis of a Memory Allocation Scheme for Implementing Stacks
An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
A Note on Gray Code and Odd-Even Merge
Amplification by Read-Once Formulas
The Complexity of Planar Counting Problems
Congruence Distributivity Implies Bounded Width
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input
Picture Skeletons Based on Eccentricities of Points of Minimum Spanning Trees
Translating Program Schemas to While-Schemas
An Approximation Algorithm for Feedback Vertex Sets in Tournaments
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Minimal-Cost Brother Trees
Erratum: Factoring Polynomials Over Algebraic Number Fields
Windows Scheduling Problems for Broadcast Systems
Expected Computation Time for Hamiltonian Path Problem
On Sets Cook-Reducible to Sparse Sets
Effective Wireless Scheduling via Hypergraph Sketches
The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model
Tree-Adjoining Language Parsing in o(n^6) Time
An Algorithm for Transitive Closure with Linear Expected Time
The "Runs" Theorem
An O(1) RMRs Leader Election Algorithm
Splitting NP-Complete Sets
Existence and Construction of Edge-Disjoint Paths on Expander Graphs
Interactive Information Complexity
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems
On Stochastic Scheduling with In-Tree Precedence Constraints
The Euclidean Orienteering Problem Revisited
Simple Confluently Persistent Catenable Lists
An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
First Order Graph Grammars
Data Movement in Odd-Even Merging
Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
On the AC 0 Complexity of Subgraph Isomorphism
Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
Geodesic Walks in Polytopes
Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
Minimum Cuts in Surface Graphs
Quicksort with Equal Keys
Online Set Packing
Communication Complexity of Computing the Hamming Distance
A Decomposition Theorem for Maximum Weight Bipartite Matchings
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs
Power Diagrams: Properties, Algorithms and Applications
Factoring Polynomials Over Algebraic Number Fields
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
A Near-Tight Approximation Algorithm for the Robot Localization Problem
A Note on Bennett's Time-Space Tradeoff for Reversible Computation
Two-Processor Scheduling with Start-Times and Deadlines
Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
Fast Parallel Computation of Polynomials Using Few Processors
Computational Complexity of the Hylland-Zeckhauser Mechanism for One-Sided Matching Markets
Axioms for the Theory of Lambda-Conversion
On Unapproximable Versions of NP-Complete Problems
Local Versus Global Properties of Metric Spaces
Locality from Circuit Lower Bounds
Compressing Interactive Communication Under Product Distributions
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Optimal Worst Case Formulas Comparing Cache Memory Associativity
Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
Short Seed Extractors against Quantum Storage
Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b -matching, and Unweighted f -factors
Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
Uniform Restricted Chase Termination
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
SPARSE Reduces Conjunctively to TALLY
Multi-Terminal 0-1 Flow
Finding an Approximate Maximum
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
3-Query Locally Decodable Codes of Subexponential Length
Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme
An o(n) Monotonicity Tester for Boolean Functions over the Hypercube
Lucid - A Formal System for Writing and Proving Programs
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
On the Computational Complexity of Program Scheme Equivalence
New Results on Linear Size Distance Preservers
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
The Complexity of Three-Way Statistical Tables
New Hardness Results for Routing on Disjoint Paths
Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups
Approximating Capacitated Routing and Delivery Problems
The Total Correctness of Parallel Programs
On the Frame--Stewart Conjecture about the Towers of Hanoi
Complete Axiomatizations for Reasoning about Knowledge and Time
Three-Player Entangled XOR Games are NP-Hard to Approximate
On Computing Algebraic Functions Using Logarithms and Exponentials
The Pure Literal Rule and Polynomial Average Time
Affine Dispersers from Subspace Polynomials
The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
Formal-Language-Constrained Path Problems
Near-Optimal Algorithms for Online Matrix Prediction
Finding Sets Covering a Point with Application to Mesh-Free Galerkin Methods
Counting Trees in a Phylogenetic Network Is \#P-Complete
Disproving the Single Level Conjecture
Free Bits, PCPs, and Nonapproximability-Towards Tight Results
On Point Location and Motion Planning among Simplices
Computing Rational Zeros of Integral Polynomials by p-adic Expansion
Learning Monotone Boolean Functions by Uniformly Distributed Examples
Splittings, Robustness, and Structure of Complete Sets
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
Bicriteria Data Compression
Average Case Analysis of Marking Algorithms
Lower Bound for the Online Bin Packing Problem with Restricted Repacking
The Complexity of Reliability Computations in Planar and Acyclic Graphs
On the Optimal Control of Two Queues with Server Setup Times and its Analysis
Lower Bounds for Restricted-Use Objects
Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
An Optimal On-Line Algorithm for k-Servers on Trees
Minimizing Disjunctive Normal Form Formulas and AC 0 Circuits Given a Truth Table
Membership in Moment Polytopes is in NP and coNP
Augmentation Problems
Bounds on the Scheduling of Typed Task Systems
Using Nondeterminism to Amplify Hardness
Lower Bounds for Accessing Binary Search Trees with Rotations
Constant-Round Interactive Proofs for Delegating Computation
On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
Definability of Languages by Generalized First-Order Formulas over N +
Transitive-Closure Spanners
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
Bounds for LPT Schedules on Uniform Processors
Additive Complexity and Zeros of Real Polynomials
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals
Query-Efficient Algorithms for Polynomial Interpolation over Composites
Generalized Connectors
Fast FPT-Approximation of Branchwidth
Amortized Communication Complexity
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
Constructing Belts in Two-Dimensional Arrangements with Applications
A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias
Random Graphs and Graph Optimization Problems
Rigorous Time/Space Trade-offs for Inverting Functions
Formal Systems for Tuple and Equality Generating Dependencies
The Power of Synchronization Mechanisms
The Complexity of Enumeration and Reliability Problems
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
Primal Beats Dual on Online Packing LPs in the Random-Order Model
Probing Convex Polygons with X-Rays
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
A Short List of Equalities Induces Large Sign-Rank
Shelf Algorithms for Two-Dimensional Packing Problems
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues
Parallel Sorting with Constant Time for Comparisons
On the Complexity of Computing Mixed Volumes
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
Uniform Interpretations of Grammar Forms
How to Morph Planar Graph Drawings
Linear and O ( n log n ) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
Toward Understanding Exclusive Read
The Category-Theoretic Solution of Recursive Domain Equations
Fast Polynomial Factorization and Modular Composition
Finding Triconnected Components by Local Replacement
Spectral Sparsification of Graphs
Semi-Online Maintenance of Geometric Optima and Measures
The Wakeup Problem
An Algorithmic Regularity Lemma for Hypergraphs
Subgroup Refinement Algorithms for Root Finding in GF(q)
Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
Round Compression for Parallel Matching Algorithms
A Decision Procedure for the First Order Theory of Real Addition with Order
On Range Searching with Semialgebraic Sets. II
A New Pebble Game That Characterizes Parallel Complexity Classes
The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
Tight Fault Locality
Reversal Complexity
Optimal File Sharing in Distributed Networks
New Upper Bounds in Klee's Measure Problem
Correct Computation Rules for Recursive Languages
Shortest Paths Without a Map, but with an Entropic Regularizer
Erratum: A Fast Monte-Carlo Test for Primality
Parallel Information Dissemination by Packets
Programmable Control of Nucleation for Algorithmic Self-Assembly
Algorithms for #BIS-Hard Problems on Expander Graphs
A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)
Improved Divide/Sort/Merge Sorting Networks
Complexity Measures for Public-Key Cryptosystems
On Resolution with Clauses of Bounded Size
Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
Conditions for Unique Graph Realizations
Approximate Solutions for the Bilinear Form Computational Problem
Synthesizing a Response Function with a Feedback Scheduling Algorithm
On Finding and Updating Spanning Trees and Shortest Paths
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
Minimizing the Number of Evaluation Passes for Attribute Grammars
Increasing the Size of a Network by a Constant Factor can Increase Performance by more than a Constant Factor
Uniform Bounds for a Class of Algebraic Mappings
The Power of Alternating One-Reversal Counters and Stacks
Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
The Serial Transitive Closure Problem for Trees
Constraint Satisfaction, Logic and Forbidden Patterns
Log-Space Polynomial End-to-End Communication
The Complexity of Symmetric Boolean Parity Holant Problems
A Rewriting System for Categorical Combinators with Multiple Arguments
An LLL Algorithm with Quadratic Complexity
Tree-Depth and the Formula Complexity of Subgraph Isomorphism
An O(n² log n) Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
Tight Revenue Gaps Among Simple Mechanisms
Generating all Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
The Power of Vacillation in Language Learning
b-Matchings in Trees
Lower Bounds on Synchronous Combinational Complexity
Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
Faster Integer Multiplication
Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
Cheeger's Inequalities for Vertex Expansion and Reweighted Eigenvalues
Maximal Rank of m x n x (mn - k) Tensors
Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
Completions of Partially Ordered Sets
Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
The Boolean Hierarchy I: Structural Properties
Convex Decomposition of Polyhedra and Robustness
A Binary Search with a Parallel Recovery of the Bits
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
Special Section on Foundations of Computer Science
Local Adjunct Languages and Regular Sets
An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
New Tight Bounds on Uniquely Represented Dictionaries
Message Multicasting in Heterogeneous Networks
Deterministic Sampling - A New Technique for Fast Pattern Matching
Tree Size by Partial Backtracking
Characterizations of Presburger Functions
Finding a Maximum Clique in an Arbitrary Graph
Asymptotic Service System Output, with Application to Multiprogramming
On the Complexity of Nash Equilibria and Other Fixed Points
A Technique for Extending Rapid Exact-Match String Matching to Arrays of More Than One Dimension
Sorting and Searching in Multisets
Nonlinear Algebra and Optimization on Rings are "Hard"
Locality in Page Reference Strings
Linear Circuits over GF(2)
On the Additive Complexity of Matrix Multiplication
Labeling Schemes for Flow and Connectivity
Upper and Lower Bounds on the Power of Advice
Erratum: Generalized Selection and Ranking: Sorted Matrices
Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
The Knuth-Bendix Completion Procedure and Thue Systems
The Complexity of Tree Automata and Logics of Programs
The Complexity of Near-Optimal Programmable Logic Array Folding
Duality Between Prefetching and Queued Writing with Parallel Disks
Expanders via Random Spanning Trees
Constructing O(n log n) Size Monotone Formulae for the k-th Threshold Function of n Boolean Variables
Space-Time Tradeoffs for Emptiness Queries
The Parametrized Complexity of Some Fundamental Problems in Coding Theory
Derandomizing Homomorphism Testing in General Groups
Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
From Gene Trees to Species Trees
Error-Resilient Optimal Data Compression
A New Approach to Planar Point Location
Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
Special Section on the Fifty-Third IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012)
Sampling Algorithms and Coresets for $\ell p Regression
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
Quantum Entanglement and Communication Complexity
Characterization of Division Algebras of Minimal Rank and the Structure of Their Algorithm Varieties
Traveling Salesman-Based Curve Reconstruction in Polynomial Time
Partially Symmetric Functions Are Efficiently Isomorphism Testable
A Generalized Class of Polynomials that are Hard to Factor
Distributional Results for Costs of Partial Match Queries in Asymmetric K-Dimensional Tries
Time-Space Tradeoffs For Undirected st -Connectivity on a Graph Automata
First-Order Queries on Finite Structures Over the Reals
Efficient Embeddings of Trees in Hypercubes
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems
The Computational Complexity of Division in Quadratic Extension Fields
On the Insertion Time of Cuckoo Hashing
A Filter Model for Concurrent lambda-Calculus
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions
Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control
Range-Efficient Counting of Distinct Elements in a Massive Data Stream
Stack Replacement Algorithms for Two-Level Directly Addressable Paged Memories
Exact-Size Sampling of Enriched Trees in Linear Time
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling
On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model
Multiparty Communication Complexity and Threshold Circuit Size of sfAC 0
Every Property of Hyperfinite Graphs Is Testable
Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
Complexity of Deciding Sense of Direction
Smallest Augmentations to Biconnect a Graph
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity
Locating Regions in a Sequence under Density Constraints
Algorithms for the Relaxed Online Bin-Packing Model
Extension Preservation Theorems on Classes of Acyclic Finite Structures
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
Fast Simulation of Turing Machines by Random Access Machines
Elastic-Degenerate String Matching via Fast Matrix Multiplication