yusuke1997/dblp-id-title huggingface dataset:
Simple and Structural Redundancy in Non-Deterministic Computation
Applicative Abstract Categorial Grammar
Translation of Simple Program Schemes
Nondeterminism in the Presence of a Diverse or Unknown Future
MANETS: High Mobility Can Make Up for Low Transmission Power
Hidden Pattern Statistics
The Online Min-Sum Set Cover Problem
Characterizations on PUNC and Precomputation (Extended Abstract)
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Multi-Stage Programming: Axiomatization and Type Safety
A Fast Algorithm for Polygon Containment by Translation (Extended Abstract)
On the Fixed-Parameter Tractability of Capacitated Clustering
Faster Regular Expression Matching
Algebraic Specifications with Generating Constraints
Quantum Automata Cannot Detect Biased Coins, Even in the Limit
Computing Measures of Weak-MSO Definable Sets of Trees
Conditions Enforcing Regularity of Context-Free Languages
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover
Time and Space Bounds for Reversible Simulation
Backdoor Sets on Nowhere Dense SAT
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard
Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II
Finite Biprefix Sets of Path in a Graph
Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems
Alphabet Reduction for Reconfiguration Problems
On Bisimilarity and Substitution in Presence of Replication
Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings
Partition Arguments in Multiparty Communication Complexity
Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming
On the Length of Strongly Monotone Descending Chains over ℕ^d
Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
A Distributed and Oblivious Heap
The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5
On the Centralizer of a Finite Set
Quantum Communication Complexity
The Complexity of Knapsack Problems in Wreath Products
Approximating Long Cycle Above Dirac's Guarantee
Completing Biprefix Codes
A Polynomial-Time Algorithm for Near-Perfect Phylogeny
Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings
An O(loglog n)-Approximation for Submodular Facility Location
Improved Approximation Algorithms for Three-Dimensional Bin Packing
A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words
Dynamic Succinct Ordered Trees
Lower Bounds for the Graph Homomorphism Problem
Recognizability Equals Definability for Partial k-Paths
Lazard's Factorizations of Free Partially Commutative Monoids
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover
For-All Sparse Recovery in Near-Optimal Time
Can A Maximum Flow be Computed on o(nm) Time?
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Flattability of Priority Vector Addition Systems
Sign-Rank Can Increase Under Intersection
The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE
Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing
Counting Homomorphisms to Square-Free Graphs, Modulo 2
Parallel and Nondeterministic Time Complexity Classes (Preliminary Report)
Parameter Estimation for Gibbs Distributions
On Recent Trends in Algebraic Specification
All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
Program Composition via Unification
Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
Deciding Knowledge in Security Protocols Under Equational Theories
A Recipe for Quantum Graphical Languages
A Cook's Tour of Countable Nondeterminism
Adaptively Secure Coin-Flipping, Revisited
Coalgebraic Predicate Logic
Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
On Reverse and General Definite Tree Languages (Extended Abstract)
Competitive Analysis of Aggregate Max in Windowed Streaming
On-the-Fly Garbage Collection: New Algorithms Inspired by Program Proofs
Regular Languages Are Church-Rosser Congruential
Leftist Grammars Are Non-primitive Recursive
Verifying a Protocol Using Relativized Bisimulation
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
On the Complexity of Simple Arithmetic Expressions
A Direct Sum Theorem in Communication Complexity via Message Compression
Extended Notions of Security for Multicast Public Key Cryptosystems
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs
Verifying and Synthesizing Software with Recursive Functions - (Invited Contribution)
Classical and Quantum Partition Bound and Detector Inefficiency
New Constructions of Mechanisms with Verification
Efficient Maximal Cubic Graph Cuts (Extended Abstract)
Semi-Streaming Algorithms for Annotated Graph Streams
The Kleene and the Parikh Theorem in Complete Semirings
Boundaries of VP and VNP
Approximation of Phrase Markers by Regular Sets
A Neuroidal Architecture for Cognitive Computation
A New Unfolding Approach to LTL Model Checking
Parameterized Data Types in Algebraic Specification Languages (Short Version)
Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes
Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
Completion of Rewrite Systems with Membership Constraints
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences
Modular System Design Applying Graph Grammars Techniques
On the Complexity of General Context-Free Language Parsing and Recognition (Extended Abstract)
Stabilizing Weighted Graphs
Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering
Universality in Quantum Computation
Building the Minimal DFA for the Set of all Subwords of a Word On-line in Linear Time
On the Resiliency of Randomized Routing Against Multiple Edge Failures
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem
A Fragment of ML Decidable by Visibly Pushdown Automata
Space Efficient Construction of Lyndon Arrays in Linear Time
Online Algorithms for Weighted Paging with Predictions
Are Stochastic Process Algebras Good for Performance and Dependability Evaluation
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
Algebraically Specified Programming Systems and Hoare's Logic
Counting in Trees for Free
A Hardware Implementation of the CSP Primitives and its Verification
Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract)
Up-to Techniques for Weak Bisimulation
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
Generic Single Edge Fault Tolerant Exact Distance Oracle
An Efficient Quantifier Elimination Procedure for Presburger Arithmetic
Tight Thresholds for Cuckoo Hashing via XORSAT
Processes Parametrised by an Algebraic Theory
Algebraic Implementation of Abstract Data Types: Concept, Syntax, Semantics and Correctness
On the Complexity of Bisimulation Problems for Basic Parallel Processes
Fault-Tolerant Rendezvous in Networks
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
A Tree Generating System
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game
Experimental Evaluation of Approximation Algorithms for the Minimum Cost Multiple-source Unsplittable Flow Problem
Testing Monotonicity over Graph Products
Automatic Generation of Multiple Exit Parsing Subroutines
The Meaning of Negative Premises in Transition System Specifications
Playing Stochastically in Weighted Timed Games to Emulate Memory
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming
Restricted Max-Min Fair Allocation
L Morphisms: Bounded Delay and Regularity of Ambiguity
Continuity and Rational Functions
Half-Positional Determinacy of Infinite Games
A Perfect Sampler for Hypergraph Independent Sets
On All Things Star-Free
An Almost Optimal Edit Distance Oracle
Axiomatizations for the Perpetual Loop in Process Algebra
A Graph-Grammar Based Approach to the Specification of Hypermedia Application Dynamics
Games with Winning Conditions of High Borel Complexity
An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces
Additional Queries to Random and Pseudorandom Oracles
Non-linear Second Order Abstract Categorial Grammars and Deletion
Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers
Intervalizing k-Colored Graphs
On Parallel Hashing and Integer Sorting (Extended Summary)
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound
Logic Programming Semantics Made Easy
The Power of Non-Rectilinear Holes
Polynomial-Space Approximation of No-Signaling Provers
Dynamic Programming Schemata
Full-Fledged Real-Time Indexing for Constant Size Alphabets
Graphical Calculi for Interaction (Abstract)
Set Membership with Two Classical and Quantum Bit Probes
Lower Bounds Are Not Easier over the Reals: Inside PH
Data Delivery by Energy-Constrained Mobile Agents on a Line
P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
Solving Recursive Net Equations
Deterministic and Game Separability for Regular Languages of Infinite Trees
Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation
Using Games and Universal Trees to Characterise the Nondeterministic Index of Tree Languages
Faster Submodular Maximization for Several Classes of Matroids
Tighter Connections Between Formula-SAT and Shaving Logs
A Calculus for Recursive Program Schemes
Determinization of Transducers over Infinite Words
Inverse Image Analysis
The Trichotomy of Regular Property Testing
Discrete-Time Control for Rectangular Hybrid Automata
Minimum Latency Submodular Cover
In-Place Suffix Sorting
Information-Theoretic Private Information Retrieval: A Unified Construction
How to Use the Minimal Separators of a Graph for its Chordal Triangulation
Computing LOGCFL Certificates
Finding Detours is Fixed-Parameter Tractable
Automata, Languages and Programming, 25th International Colloquium, ICALP'98, Aalborg, Denmark, July 13-17, 1998, Proceedings
On the Sensitivity Conjecture
Decidable Fragments of Simultaneous Rigid Reachability
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
FO Logic on Cellular Automata Orbits Equals MSO Logic
Conditional Dependencies for Horizontal Decompositions
On Interactive Proofs with a Laconic Prover
Symmetric Strategy Improvement
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
Computing Shortest Paths and Distances in Planar Graphs
Extended Transition Systems for Parametric Bisimulation
Improved Submatrix Maximum Queries in Monge Matrices
On the Study Data Structures: Binary Tournaments with Repeated Keys
New Techniques for Universality in Unambiguous Register Automata
On Everlasting Security in the Hybrid Bounded Storage Model
Strong Inapproximability of the Basic k -Spanner Problem
Adaptive Pattern Matching
Compact Routing Tables for Graphs of Bounded Genus
Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines
When the Optimum is also Blind: a New Perspective on Universal Optimization
Reversible Flowchart Languages and the Structured Reversible Program Theorem
Low-Bandwidth Routing and Electrical Power Networks
Stochastic Vehicle Routing with Recourse
Present-Day Hoare-Like Systems for Programming Languages with Procedures: Power, Limits and most Likely Expressions
Expressive Power of Pebble Automata
Deterministic and Las Vegas Primality Testing Algorithms
On Three Types of Unambiguity of Context-Free Languages
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence
Quantitative Analysis of Probabilistic Lossy Channel Systems
Coloring Circular Arcs with Applications
Optimal In-place Sorting of Vectors and Records
Coboundary and Cosystolic Expansion from Strong Symmetry
Comparison-Free Polyregular Functions
A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications
A Combinatorial Theorem for Trees
A Hierarchy of Equivalences for Asynchronous Calculi
On Structural Similarity of Phrase-Structure Languages
Characterizing Definability in Decidable Fixpoint Logics
Computability on the Probability Measures on the Borel Sets of the Unit Interval
Testing Forest-Isomorphism in the Adjacency List Model
On Graph Problems in a Semi-streaming Model
The Geometry of Tree-Based Sorting
Local Computation Algorithms for Hypergraph Coloring - Following Beck's Approach
Contractions in Comparing Concurrent Semantics
Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time
Preemptive Scheduling in Overloaded Systems
Trading Bounds for Memory in Games with Counters
Algebraic Semantics of Recursive Flowchart Schemes
Event Structure Semantics for CCS and Related Languages
Scheduling for Speed Bounded Processors
Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem - (Extended Abstract)
A Faster Construction of Greedy Consensus Trees
Tight Approximation Algorithm for Connectivity Augmentation Problems
Submodular Cost Allocation Problem and Applications
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
New Data Structures for Subgraph Connectivity
Factors of Words
Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II
On the Average Stack Size of Regularly Distributed Binary Trees
Broadcasting with Random Matrices
Parsing Context-Sensitive NCE Graph Grammars
Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete
Interactive Observability in Ludics
On the Equivalence of -Automata
A Domain for Concurrent Termination: A Generalization of Mazurkiewicz Traces (Extended Abstract)
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
On Randomized Online Labeling with Polynomially Many Labels
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
Characterization of Temporal Property Classes
Optimal Short Cycle Decomposition in Almost Linear Time
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II
Localization for a System of Colliding Robots
Belief Propagation Guided Decimation on Random k-XORSAT
Complexity of Decoding Positive-Rate Reed-Solomon Codes
Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
Online Disjoint Spanning Trees and Polymatroid Bases
Discrete Tomography: Reconstruction under Periodicity Constraints
Testing Similar Means
Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity
Completeness Rules for Reachability, Containment, and Equivalence, with Respect to Conflict-Free Vector Replacement Systems
Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields
Symmetric Arithmetic Circuits
A New Universal Class of Hash Functions and Dynamic Hashing in Real Time
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets
Functional Dependencies and Disjunctive Existence Constraints in Database Relations with Null Values
A Constructive Approach to Compiler Correctness
A Mahler's Theorem for Word Functions
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Generic Expression Hardness Results for Primitive Positive Formula Comparison
Lower Bounds for the Space Complexity of Context-Free Recognition
Private and Continual Release of Statistics
On the Power of k -Consistency
Information Flow in Concurrent Games
A PTAS for Capacitated Vehicle Routing on Trees
Testing Properties of Sets of Points in Metric Spaces
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification
Time Lower Bounds For CREW-PRAM Computation Of Monotone Functions
On Families of Graphs Having a Decidable First Order Theory with Reachability
On the Complexity of Client-Waiter and Waiter-Client Games
Equivalences for Fair Kripke Structures
A (2+\epsilon ) ( 2 + ϵ ) -Approximation Algorithm for the Storage Allocation Problem
Unique Assembly Verification in Two-Handed Self-Assembly
Fully Functional Parameterized Suffix Trees in Compact Space
Molecular Assembly and Computation: From Theory to Experimental Demonstrations
Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks
Real Time Agents
How to Get Rid of Pseudoterminals
Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time
On Modular Properties of Higher Order Extensional Lambda Calculi
On the Complexity of Searching in Trees: Average-Case Minimization
Cryptographically Sound Implementations for Communicating Processes
A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers
List Update with Delays or Time Windows
Light Spanners
Automated Synthesis of Distributed Controllers
Combining Binary Search Trees
The Positive Semidefinite Grothendieck Problem with Rank Constraint
Quantum Chebyshev's Inequality and Applications
Church-Rosser Languages vs. UCFL
On the Number of Random Bits in Totally Private Computation
All-Instances Termination of Chase is Undecidable
Faithful Loops for Aperiodic E-Ordered Monoids
Complexity Classes of Alternating Machines with Oracles
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
Intersection of Regular Languages and Star Hierarchy
Sophistication Revisited
Converting Online Algorithms to Local Computation Algorithms
ICALP Workshops 2000, Proceedings of the Satelite Workshops of the 27th International Colloquium on Automata, Languages and Programming, Geneva, Switzerland, July 9-15, 2000
Concurrent Zero Knowledge in the Public-Key Model
Length-Bounded Cuts and Flows
Dynamic Complexity of Directed Reachability and Other Problems
Time and Parallelizability Results for Parity Games with Bounded Treewidth
Compressed Tree Canonization
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Coeffects: Unified Static Analysis of Context-Dependence
Weak Parity
Special Relations in Automated Deduction
Strong Abstract Interpretation Using Power Domains (Extended Abstract)
Revisiting the Correspondence between Cut Elimination and Normalisation
Subpolynomial Complexity Classes of Real Functions and Real Numbers
Improved Algorithms for Latency Minimization in Wireless Networks
Domain Reasoning in TopKAT
Proving Programs Incorrect
Outsourced Pattern Matching
On the Identity Problem for the Special Linear Group and the Heisenberg Group
The Global Power of Additional Queries to p-Random Oracles
Toward Model Theory with Data Values
Computational Depth and Reducibility (Extended Abstract)
On the Size of Finite Rational Matrix Semigroups
Finite Delay Solutions for Sequential Conditions
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves
Distance Labels with Optimal Local Stretch
On the Metric-Based Approximate Minimization of Markov Chains
Approximating Markov Processes by Averaging
One-Round Secure Computation and Secure Autonomous Mobile Agents
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
Refuting Approaches to the Log-Rank Conjecture for XOR Functions
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices
Transductions of Context-Free Languages into Sets of Sentential Forms
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Derivations et Redutions dans les Grammaires Algebriques
A Total AC-Compatible Reduction Ordering on Higher-Order Terms
Real Computations with Fake Numbers
Genus Characterizes the Complexity of Graph Problems: Some Tight Results
On a Conjecture of J. Shallit
Axiomatising Divergence
Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
Linear Time and Branching Time Semantics for Recursion with Merge
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
Characterization of High Level Tree Transducers
Optimal Lower Bounds for Rank and Select Indexes
Equational Formulas in Order-Sorted Algebras
Contention Issues in Congestion Games
"Natural" Complexity Measures and Time versus Memory: Some Definitional Proposals
Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction (Preliminary Version)
Rational Equivalence Relations
Modelling Mobility: A Discrete Revolution
A Finite Equational Base for CCS with Left Merge and Communication Merge
Macro Grammars, Lindenmayer Systems and Other Copying Devices
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
Testing Core Membership in Public Goods Economies
Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes
Graph Similarity and Homomorphism Densities
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization
Action Codes
The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem
Dynamic Diffusion Load Balancing
Turing Machines with Associative Memory Access
Complete and Tractable Local Linear Time Temporal Logics over Traces
Robust Algorithms for TSP and Steiner Tree
Bandwidth Efficient Parallel Computation
Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Towards Optimal Set-Disjointness and Set-Intersection Data Structures
Combinatorial Problems, Combinator Equations and Normal Forms
Near-Optimal Algorithm for Constructing Greedy Consensus Tree
Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine
Circuit Complexity and the Expressive Power of Generalized First-Order Formulas
Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler
Reachability Switching Games
Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
Histogramming Data Streams with Fast Per-Item Processing
Optimal Quantum Adversary Lower Bounds for Ordered Search
A lambda-Calculus for Resource Separation
Fixed Point Computation Problems and Facets of Complexity (Invited Talk)
Sleep Management on Multiple Machines for Energy and Flow Time
Tiling Random Regular Graphs Efficiently
Model Theory Makes Formulas Large
Characteristic Formulae
On the Complexity and Inapproximability of Shortest Implicant Problems
Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth
Polylogarithmic-Time Leader Election in Population Protocols
Some Results on Effective Randomness
Analytic Variations on the Common Subexpression Problem
Tight Size Bounds for Packet Headers in Narrow Meshes
A Robust APTAS for the Classical Bin Packing Problem
On the Approximability of Average Completion Time Scheduling under Precedence Constraints