yusuke1997/dblp-id-title huggingface dataset:
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
Parallel Graph Algorithms that Are Efficient on Average
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP
High-precision Estimation of Random Walks in Small Space
A Theory of Using History for Equational Systems with Applications (Extended Abstract)
Implicit Data Structures with Fast Update (Preliminary Report)
Parallel Communication with Limited Buffers (Preliminary Version)
Logical Reducibility and Monadic NP
Tight Space Complexity of the Coin Problem
On the Power of Interaction
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems
Which Regular Expression Patterns Are Hard to Match?
Counting Bottlenecks to Show Monotone P <=> NP
Dynamic Scheduling on Parallel Machines
The Union of Convex Polyhedra in Three Dimensions
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
An O(c^k n) 5-Approximation Algorithm for Treewidth
63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022
k+1 Heads Are Better than k
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Knuth Prize
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
Conjunctive Encoding of Boolean Matrices
How to Learn an Unknown Environment (Extended Abstract)
Application of a Planar Separator Theorem
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
Combinatorial Contracts
Optimal Resilience Proactive Public-Key Cryptosystems
Succinct Representation, Random Strings, and Complexity Classes
Multivalued logic devices for simulating threshold neurons
Population Recovery and Partial Identification
On Approximating the Radii of Point Sets in High Dimensions
A Separator Theorem in Minor-Closed Classes
Bit Encryption Is Complete
62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022
Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability
Reductions, Codes, PCPs, and Inapproximability
Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
Many-valued logics and reliable homeostatic mechanisms
A Theory of PAC Learnability of Partial Concept Classes
How to Go Beyond the Black-Box Simulation Barrier
Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking
Some Theoretical Aspects of Position-Location Problems
On the Complexity of Two-PlayerWin-Lose Games
An Approach to a Unified Theory of Automata
Mechanisms for a No-Regret Agent: Beyond the Common Prior
How to Generate and Exchange Secrets (Extended Abstract)
Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version)
An Omega(n 1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs
One-Way Log-Tape Reductions
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap
18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
Kernel Density Estimation through Density Constrained Near Neighbor Search
Meanders, Ramsey Theory and Lower Bounds for Branching Programs
Random Order Contention Resolution Schemes
Computing Blindfolded: New Developments in Fully Homomorphic Encryption
Noise Tolerance of Expanders and Sublinear Expander Reconstruction
Efficient Uses of the Past
Testing that distributions are close
Motif Cut Sparsifiers
On Recursive Equations Having a Unique Solution
The Complexity of the Approximation of the Bandwidth Problem
How to Achieve Non-Malleability in One or Two Rounds
Robust Testing of Lifted Codes with Applications to Low-Degree Testing
Sensitive Functions and Approximate Problems
Checking the Correctness of Memories
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Sparse Affine-Invariant Linear Codes Are Locally Testable
Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract)
Traveling with a Pez Dispenser (Or, Routing Issues in MPLS)
AdWords in a Panorama
Algorithms and Hardness for Linear Algebra on Geometric Graphs
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity
Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems
On the Complexity of a Set-Union Problem
Fully Dynamic Maximal Matching in Constant Update Time
Parameterized Approximation Schemes for Clustering with General Norm Objectives
Bounded-transient automata
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)
On Certain Connectivity Properties of the Internet Topology
An Algorithm for Minimizing Read Only Memories for Machine Control
Transition Graphs and the Star Height Problem
A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity
SDP Integrality Gaps with Local ell_1-Embeddability
Rounds vs Communication Tradeoffs for Maximal Independent Sets
MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Edge-Weighted Online Bipartite Matching
Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
Using Autoreducibility to Separate Complexity Classes
The Kikuchi Hierarchy and Tensor PCA
Bounds on the Permanent and Some Applications
On the minimum stage realization of switching functions using logic gates with limited fan-in
Optimization Problems in Congestion Control
Bin Packing with Items Uniformly Distributed over Intervals [a,b]
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
Refining a Triangulation of a Planar Straight-Line Graph to Eliminate Large Angles
Towards Optimal Distributed Consensus (Extended Abstract)
The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Spectral Gap and log-Sobolev Constant for Balanced Matroids
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
On the Power of Discrete and of Lexicographic Helly-Type Theorems
A Tight Lower Bound for k-Set Agreement
Higher Eigenvalues of Graphs
Synchronization power depends on the register size (Preliminary Version)
Certified Hardness vs. Randomness for Log-Space
Understanding Alternating Minimization for Matrix Completion
Universal Single Transition Time Asynchronous State Assignments
An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices
Dynamic Deterministic Constant-Approximate Distance Oracles with n ε Worst-Case Update Time
Algebraic Families of Interpretations
The Closest Substring problem with small distances
Theory and Applications of Trapdoor Functions (Extended Abstract)
New Lower Bounds for Adaptive Tolerant Junta Testing
Strategic Network Formation through Peering and Service Agreements
On the Complexity of Real Functions
Smoothing the gap between NP and ER
A Primal-Dual Randomized Algorithm for Weighted Paging
Fairness in Routing and Load Balancing
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation
Waste Makes Haste: Tight Bounds for Loose Parallel Sorting
The Randomness Complexity of Parallel Repetition
Hierarchical Memory with Block Transfer
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
How to Recycle Random Bits
An Algebraic Proof of a Robust Social Choice Impossibility Theorem
Streaming Euclidean k-median and k-means with o(log n) Space
Field Extension and Triangular Aggregating, Uniting and Canceling for the Acceleration of Matrix Multiplications
Canonical Labelling of Graphs in Linear Average Time
Turing Machines with Several Read-Write Heads (Preliminary Report)
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries
Linear Hashing Is Awesome
SETH-Hardness of Coding Problems
Fast Deterministic Fully Dynamic Distance Approximation
A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs
Markov Layout
Rational Algebraic Theories and Fixed-Point Solutions
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
Permuting
An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract)
Problems in the physical realization of speed independent circuits
Coordinate Methods for Matrix Games
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications
Asynchronous Control Networks
The Maintenance of Common Data in a Distributed System
A Fourier-Analytic Approach to Reed-Muller Decoding
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Taking a Walk in a Planar Arrangement
Optimal Approximate Distance Oracle for Planar Graphs
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
The Load, Capacity and Availability of Quorum Systems
Tight Bounds for Online Edge Coloring
Deterministic Extractors for Affine Sources over Large Fields
Formal Languages: Origins and Directions
Faster Isomorphism Testing of p-Groups of Frattini Class 2
Precise Bounds for Presburger Arithmetic and the Reals with Addition: Preliminary Report
Multiparty Communication Complexity and Threshold Circuit Size of AC^0
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Saving Space in Fast String-Matching
Computing Nash Equilibria: Approximation and Smoothed Complexity
A Polynomial Time Algorithm for Counting Integral Points in Polyhedra when the Dimension Is Fixed
Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams
Everywhere-Sparse Spanners via Dense Subgraphs
A Decidable mu-Calculus: Preliminary Report
An Improved Line-Point Low-Degree Test
A d 1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
Indistinguishability Obfuscation from Functional Encryption
Improved Condensers for Chor-Goldreich Sources
Synchronizing and Representation Problems for Sequential Machines with Masked Outputs
A New Decidable Problem, with Applications (Extended Abstract)
The Complexity of Compacting Hierarchically Specified Layouts of Integrated Circuits (Preliminary Version)
On Classes of Program Schemata
Computable Nondeterministic Functions
On Networks of Noisy Gates
Randomized Self-Assembly for Exact Shapes
Existential Second-Order Logic over Graphs: Charting the Tractability Frontier
Graph Connectivities, Network Coding, and Expander Graphs
Complexity of Partial Satisfaction
On the Computational Power of Some Machines with Pushdown-Like Storage
Diversity-Based Inference of Finite Automata (Extended Abstract)
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version)
A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes
Incremental Planarity Testing (Extended Abstract)
A constant rate non-malleable code in the split-state model
Agnostically Learning under Permutation Invariant Distributions
Learning DNF from Random Walks
LP Rounding for k-Centers with Non-uniform Hard Capacities
On e-Biased Generators in NC0
Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version)
Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs
Efficient Distribution-free Learning of Probabilistic Concepts (Extended Abstract)
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract)
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component
Fully Dynamic Biconnectivity in Graphs
On the Number of Multiplications for the Evaluation of a Polynomial and All Its Derivatives
Fault-Tolerant Distributed Computing in Full-Information Networks
Proofs of Space with Maximal Hardness
Recognizing Certain Repetitions and Reversals Within Strings
Average-case Complexity
I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs
Division Is Good
A Characterization of NC by Tree Recurrence
Determining the best ordering of variables in cascade switching circuits
Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$
Estimating the Size of the Transitive Closure in Linear Time
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
Randomly Coloring Constant Degree Graphs
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design
Quantum Information and the PCP Theorem
Structuring labeled trees for optimal succinctness, and beyond
On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract)
Naively Sorting Evolving Data is Optimal and Robust
Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut
Quadratic Goldreich-Levin Theorems
Robust Traceability from Trace Amounts
Parallel Repetition from Fortification
Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract)
Linear Systems over Composite Moduli
Threesomes, Degenerates, and Love Triangles
Balls and Bins: Smaller Hash Families and Faster Evaluation
Lattice Problems in NP cap coNP
(Meta) Kernelization
Parallel computable higher type functionals (Extended Abstract)
On Determinism versus Non-Determinism and Related Problems (Preliminary Version)
Topological Persistence and Simplification
Current-operated diode logic gates
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Agnostically Learning Multi-Index Models with Queries
Uniform Generation of Random Regular Graphs
Complexity Classification of Local Hamiltonian Problems
Approximating Shortest Paths on an Nonconvex Polyhedron
Universality in Cellular Automata
Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees
Hierarchy Theorems for Probabilistic Polynomial Time
Mutual Exclusion with O(log^2 Log n) Amortized Work
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
On-Line Confidence Machines Are Well-Calibrated
Low Treewidth Embeddings of Planar and Minor-Free Metrics
An Automatic Inequality Prover and Instance Optimal Identity Testing
On computability by certain classes of restricted Turing machines
Testing Expansion in Bounded-Degree Graphs
Universal Two State Machines: Characterization Theorems and Decomposition Schemes
Delayed-logic and finite-state machines
A Linear History Semantics for Distributed Languages (Extended Abstract)
Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees
Quantum Walk Algorithm for Element Distinctness
Tight Bounds for Depth-two Superconcentrators
The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract)
A General Approach to Removing Degeneracies
On the Predictability of Coupled Automata: An Allegory about Chaos
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete
Efficient Self-Testing/Self-Correction of Linear Recurrences
Near-Optimal Conversion of Hardness into Pseudo-Randomness
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations
On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract)
A Class of Logic Problems Solvable by Linear Programming
Stability of Adversarial Queues via Fluid Models
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling
On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract)
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Approximately Counting Triangles in Sublinear Time
Equivalence in Finite-Variable Logics is Complete for Polynomial Time
A New Pebble Game that Characterizes Parallel Complexity Classes
Syntax Directed Transduction
Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines
Packing 2-Dimensional Bins in Harmony
Three-Source Extractors for Polylogarithmic Min-Entropy
0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms
Approximate Shape Fitting via Linearization
Machine properties preserved under state minimization
The Decidability of the Equivalence of Context-Free Grammar Forms
Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths
Approximate Algorithms for the Traveling Salesperson Problem
From Grassmannian to Simplicial High-Dimensional Expanders
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
Inferring Evolutionary History from DNA Sequences (Extended Abstract)
Harmonic Persistent Homology (extended abstract)
Bounds on Monotone Switching Networks for Directed Connectivity
Memory bounds for recognition of context-free and context-sensitive languages
Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic
Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time
Universally Composable Protocols with Relaxed Set-Up Assumptions
Gages Accept Concurrent Behavior
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
On the Lower Envelope of Bivariate Functions and its Applications
Median Selection Requires (2+epsilon)n Comparisons
Stability and Replicability in Learning
Quasi-optimal Multiplication of Linear Differential Operators
An Algebraic Approach to Non-malleability
Competitive Algorithms for Layered Graph Traversal
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
Tight Lower Bounds for the Distinct Elements Problem
On Bounded Queries and Approximation
A 7/8-Approximation Algorithm for MAX 3SAT?
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
Heavy Hitters via Cluster-Preserving Clustering
On the Average-Case Hardness of CVP
QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method
Metric Sublinear Algorithms via Linear Sampling
An Additive Combinatorics Approach Relating Rank to Communication Complexity
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Program Schemata as Automata: Part I
Explicit Construction of Natural Bounded Concentrators
The Emptiness Problem for Automata on Infinite Trees
On the Equivalence of Asynchronous Control Structures
Random Walks That Find Perfect Objects and the Lovasz Local Lemma
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Inferring Local Homology from Sampled Stratified Spaces
Algorithmic Applications of Low-Distortion Geometric Embeddings
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums
Competitive k-Server Algorithms (Extended Abstract)
Counting Small Induced Subgraphs Satisfying Monotone Properties
On the Quantitative Hardness of CVP
Faster Generation of Random Spanning Trees
Parametric and Kinetic Minimum Spanning Trees
Sequencing Tasks in Multiprocess Systems to Avoid Deadlocks
Local List Decoding with a Constant Number of Queries
The Communication Complexity of Distributed epsilon-Approximations
Verifying Temporal Properties of Finite-State Probabilistic Programs
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
Achievable Cases in an Asynchronous Environment (Extended Abstract)
On Worst-Case to Average-Case Reductions for NP Problems
Traversing combinatorial 0/1-polytopes via optimization
Non-positive Curvature and the Planar Embedding Conjecture
The Price of Explainability for Clustering
Optimal Simulations of Tree Machines (Preliminary Version)
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Asynchronous PRAMs Are (Almost) as Good as Synchronous PRAMs
Discrepancy and epsilon-approximations for bounded VC-dimension
Testing Polynomials over General Fields
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
The Complexity of Parallel Prefix Problems on Small Domains
Undirected Connectivity in O(log ^1.5 n) Space
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
Witnesses for non-satisfiability of dense random 3CNF formulas
Fully Abstract Models of the Lazy Lambda Calculus
Coresets forWeighted Facilities and Their Applications
Geometric Discrepancy Revisited
Black-Box Garbled RAM
Maximum Likelihood Decoding of Reed Solomon Codes
Complexity of Trie Index Construction (Extended Abstract)
Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results
Rapid mixing of Glauber dynamics via spectral independence for all degrees
Private Codes or Succinct Random Codes That Are (Almost) Perfect
Robust Polynomial Regression up to the Information Theoretic Limit
Adaptive Seeding in Social Networks
Sharp Mixing Time Bounds for Sampling Random Surfaces
On Derandomizing Local Distributed Algorithms
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract)
On maximum stability realizations of linearly separable Boolean functions
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC
Approximating ATSP by Relaxing Connectivity
Tight Bounds for General Computation in Noisy Broadcast Networks
On Monotone Formula Closure of SZK
The Equivalence Problem for Regular Expressions over one Letter Is Elementary
Space-Efficient Framework for Top-k String Retrieval Problems
Random Polynomial Time Is Equal to Slightly-random Polynomial Time
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets
Improved Average-Case Lower Bounds for DeMorgan Formula Size
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract)
New Unconditional Hardness Results for Dynamic and Online Problems
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs
Evolution with Recombination
Unique Sink Orientations of Cubes
The Grothendieck Constant is Strictly Smaller than Krivine's Bound
A Unified Analysis of Paging and Caching