yusuke1997/dblp-id-title huggingface dataset:
Combinatorial Algorithms for the Generalized Circulation Problem
Quantum Query Complexity of State Conversion
Finely-Competitive Paging
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma
Limited Random Access Turing Machines
On Matrix Multiplication and Polynomial Identity Testing
Some Triply-Logarithmic Parallel Algorithms (Extended Abstract)
Shuffling by Semi-Random Transpositions
The Position of Table Languages within the Hierarchy of Nondeterministic On-Line Tape-Bounded Turing Machine Languages
A time and space optimal stable population protocol solving exact majority
Constructive Separations and Their Consequences
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
Bounds on the Cover Time (Preliminary Version)
On the Complexity of Comparison Problems using Linear Functions (Preliminary Report)
Terminal Embeddings in Sublinear Time
Incrementally Verifiable Computation via Rate-1 Batch Arguments
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments
Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs
Classes of Automata and Transitive Closure
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem
Complete and Incomplete Randomized NP Problems
Submodular Function Minimization under Covering Constraints
Welfare Maximization with Limited Interaction
A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract)
Temporal Logic Can Be More Expressive
Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding
Subexponential Algorithms for Unique Games and Related Problems
Learning mixtures of product distributions over discrete domains
Robust Fourier and Polynomial Curve Fitting
The Computational Complexity of Simultaneous Diophantine Approximation Problems
A Parallel-Acting Iterative Automaton
Probabilistic Checking of Proofs; A New Characterization of NP
On multi-head finite automata
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
Geometrical Realization of Set Systems and Probabilistic Communication Complexity
Observations about the Development of Theoretical Computer Science
On the Complexity of Learning From Counterexamples (Extended Abstract)
Hardness Magnification for all Sparse NP Languages
Mechanism Design via Machine Learning
Computational Efficiency Requires Simple Taxation
The Relationship between Public Key Encryption and Oblivious Transfer
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier
Optimal Lower Bounds for Quantum Automata and Random Access Codes
More on Average Case vs Approximation Complexity
Minor Containment and Disjoint Paths in Almost-Linear Time
Optimal Algorithms for Curves on Surfaces
A Primitive Recursive Algorithm for the General Petri Net Reachability Problem
Hop-Constrained Metric Embeddings and their Applications
Truly Alphabet-Independent Two-Dimensional Pattern Matching
Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values
On the Hardness of Optimal Auctions
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Representations of Rational Functions
Non-Complex Sequences: Characterizations and Examples
The Inverse of an Automorphism in Polynomial Time
Turing machine recognizers for general rewriting systems
Active Property Testing
Non-malleable Codes against Constant Split-State Tampering
Computing Simulations on Finite and Infinite Graphs
60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
Zero-Knowledge Proof Systems for QMA
Linear Congruential Generators Do Not Produce Random Sequences
Nearly Optimal List Labeling
Matrix Decomposition Problem Is Complete for the Average Case
Optimum Algorithms for Two Random Sampling Problems (Extended Abstract)
On the Value of Information in Coordination Games (preliminary version)
Learning One-Counter Languages in Polynomial Time (Extended Abstract)
Canonical decompositions of 3-connected graphs
Nearly Tight Bounds for Wormhole Routing
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
On Sets of Numbers Recognized by Push-Down Automata
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Scaling Algorithms for Network Problems
Market Equilibrium via a Primal-Dual-Type Algorithm
55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014
Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem
Skeletal LR Parsing
Non-Malleable Commitments using Goldreich-Levin List Decoding
A Lower Bound for Matrix Multiplication
A Group-Theoretic Approach to Fast Matrix Multiplication
Static Optimality Theorem for External Memory String Access
Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
Commitments are Equivalent to Statistically-Verifiable One-Way State Generators
Inferring a Sequence Generated by a Linear Congruence
Testing Graph Properties with the Container Method
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
Tight Analyses of Ordered and Unordered Linear Probing
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
A Single-Exponential Time 2-Approximation Algorithm for Treewidth
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
Almost 3-Approximate Correlation Clustering in Constant Rounds
Near Optimal Memory-Regret Tradeoff for Online Learning
Faster Algorithms for the Generalized Network Flow Problem
A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces
On Context-Free Generators
Edge-Disjoint Routing in Plane Switch Graphs in Linear Time
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices
Algorithms and Complexity Results for #SAT and Bayesian Inference
Randomized Multidimensional Search Trees: Lazy Balancing and Dynamic Shuffling (Extended Abstract)
Full Abstraction for Nondeterministic Dataflow Networks
Fault Diagnosis of Logical Circuits
Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract)
Noisy Interactive Quantum Communication
Lower Bounds by Probabilistic Arguments (Extended Abstract)
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
On Approximating Cutwidth and Pathwidth
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
Enumerating the k Closest Pairs Optimally
Optimal Scheduling on Multi-Processor Computing Systems
Separations in Proof Complexity and TFNP
Pseudorandom Generators for Read-Once Branching Programs, in Any Order
Edit Distance: Sketching, Streaming, and Document Exchange
Approximating the single source unsplittable min-cost flow problem
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
Dispersers for Affine Sources with Sub-polynomial Entropy
Verifiable Random Functions
Vickrey Prices and Shortest Paths: What is an Edge Worth?
A Space Efficient Method for the Lowest Common Ancestor Problem and an Application to Finding Negative Cycles
Dependent Rounding in Bipartite Graphs
On the characterization of threshold functions
Back to the Future: Towards a Theory of Timed Regular Languages
Accelerated Newton Iteration for Roots of Black Box Polynomials
Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract)
Optimal Testing of Multivariate Polynomials over Small Prime Fields
Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions
Balancing Straight-Line Programs
Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits
Delegating Computations with (Almost) Minimal Time and Space Overhead
Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering
Parallel Leveled Grammars
Contention Resolution with Guaranteed Constant Expected Delay
Linear Verification for Spanning Trees
Mappings of languages by two-tape devices
States of sequential machines whose logical elements involve delay
Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Subexponential LPs Approximate Max-Cut
Fast Broadcasting and Gossiping in Radio Networks
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem
Proof of the Clustered Hadwiger Conjecture
Eigenvalues and Graph Bisection: An Average-Case Analysis (Extended Abstract)
Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs
FOCS 2005 - Copyright
Simulations among Multidimensional Turing Machines (Preliminary Version)
Tree Data Structures for N-Body Simulation
Characterizations of LR(0) Languages (Extended Abstract)
Lower Bounds for Monotone Span Programs
Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
Efficiently Learning Mixtures of Mallows Models
Capacity Threshold for the Ising Perceptron
Residual Based Sampling for Online Low Rank Approximation
Some new results on the analysis and reliability of large polyfunctional nets
Resettably-Sound Zero-Knowledge and its Applications
On the Exponent of the All Pairs Shortest Path Problem
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
Improved Dynamic Reachability Algorithms for Directed Graphs
Optimization among Provably Equivalent Programs (Preliminary Abstract)
Privacy Amplification by Iteration
A Scaling Algorithm for Weighted Matching on General Graphs
The Subspace Flatness Conjecture and Faster Integer Programming
Bounds for Small-Error and Zero-Error Quantum Algorithms
Query lower bounds for log-concave sampling
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications
Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results
On Selecting a Satisfying Truth Assignment (Extended Abstract)
Communication-Optimal Maintenance of Replicated Information
Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint
On the Security of Public Key Protocols (Extended Abstract)
A Phenomenon in the Theory of Sorting
On the Power of Quantum Finite State Automata
Minimization of Fanout in Switching Networks
Improved Online Algorithm for Weighted Flow Time
When Does Adaptivity Help for Quantum State Learning?
Two-Dimensional Formal Languages and Pattern Recognition by Cellular Automata
Entanglement is Necessary for Optimal Quantum Property Testing
Safe and Effective Determinant Evaluation
Transient behavior in iterative combinatorial switching networks
On Pseudolinear Codes for Correcting Adversarial Errors
Dense and Non-Dense Families of Complexity Classes
Cryptographic Hardness for Learning Intersections of Halfspaces
Rarity for Semimeasures
A (fairly) Simple Circuit that (usually) Sorts
Using Clerks in Parallel Processing
Semantic Models for Second-Order Lambda Calculus
NAND Cellular Arrays
Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)
An XOR Lemma for Deterministic Communication Complexity
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
Optimal System of Loops on an Orientable Surface
Approximate Kernel Clustering
48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, USA, October 20-23, 2007, Proceedings
Optimal Induced Universal Graphs and Adjacency Labeling for Trees
Two-Message Quantum Interactive Proofs Are in PSPACE
Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?"
Canonical Labeling of Regular Graphs in Linear Average Time
Weak Random Sources, Hitting Sets, and BPP Simulations
Property Grammars and Table Machines
42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001
Shortest Path Problems in Planar Graphs (Preliminary Version)
EPTAS for Max Clique on Disks and Unit Balls
Delaunay Graphs are Almost as Good as Complete Graphs
On the Algebra of Order (Extended Abstract)
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes
Some theorems for incompletely specified sequential machines with applications to state minimization
Flipping coins in many pockets (Byzantine agreement on uniformly random values)
Sensitive Distance and Reachability Oracles for Large Batch Updates
On the Representation of Formal Languages Using Automata on Networks
A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables per Inequality
Unstructured Hardness to Average-Case Randomness
Fault-tolerant Wait-free Shared Objects
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Element Distinctness, Frequency Moments, and Sliding Windows
Fusible HSTs and the Randomized k-Server Conjecture
Input-Indistinguishable Computation
Hazard detection in combinational and sequential switching circuits
Planning for Fast Connectivity Updates
Approximate Representation Theory of Finite Groups
Lower Bounds for Accessing Binary Search Trees With Rotations (Preliminary Version)
Some Relationships between Logics of Programs and Complexity Theory (Extended Abstract)
Improved Extractors for Small-Space Sources
On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs
Explicit orthogonal and unitary designs
Towards Separating Nondeterministic Time from Deterministic Time
8th Annual Symposium on Switching and Automata Theory, Austin, Texas, USA, October 18-20, 1967
Hardness of Buy-at-Bulk Network Design
The Complexity and Distribution of Hard Problems (Extended Abstract)
Certifying Almost All Quantum States with Few Single-Qubit Measurements
Augmenting Graphs to Meet Edge-Connectivity Requirements
Knuth Prize Lecture: Complexity of Communication in Markets
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits
Synthesis of combinational logic using three-input majority gates
On Relations Between Input and Communication/Computation in VLSI (Preliminary Report)
Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States
On the Complexity of Learning from Counterexamples and Membership Queries
Near-Optimal Sparse Recovery in the L1 Norm
The Loading Time Scheduling Problem (Extended Abstract)
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness
Minimal sums for Boolean functions having many unspecified fundamental products
On Weighted Graph Sparsification by Linear Sketching
On the Complexity of Avoiding Heavy Elements
Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors
24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983
Economy of Descriptions by Parsers, DPDA's, and PDA's
A (log n) Omega(1) Integrality Gap for the Sparsest Cut SDP
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n 5/4 ) Rounds
On the Complexity of Kinodynamic Planning
Approximate Algorithms for Optimization of Busy Waiting in Parallel Programs (Preliminary Report)
Derandomization of Sparse Cyclotomic Integer Zero Testing
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting
Exponential Separations Between Learning With and Without Quantum Memory
Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus
Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties
On Uniform Circuit Complexity (Extended Abstract)
Hash Functions for Priority Queues
Efficient Fully Homomorphic Encryption from (Standard) LWE
Efficient Inference of Partial Types
On the Exact Learning of Formulas in Parallel (Extended Abstract)
The Graph Minor Algorithm with Parity Conditions
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
Jitter Control in QoS Networks
Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents
Fast Parallel Computation with Permutation Groups
Quantum Cryptography with Imperfect Apparatus
Hardness of Approximate Diameter: Now for Undirected Graphs
Dynamic Planar Convex Hull
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract
Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve (Extended Abstract)
Two Query PCP with Sub-Constant Error
A Fast Algorithm for Multiprocessor Scheduling
Computing in Anonymous Dynamic Networks Is Linear
Search Problems in the Decision Tree Model (Preliminary Version)
Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound
Stability and Efficiency of a Random Local Load Balancing Protocol
Polynomial Simulations of Decohered Quantum Computers
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
A Deterministic Parallel Algorithm for Planar Graphs Isomorphism
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
Additive Approximation for Edge-Deletion Problems
Transformation of Program Schemes to Standard Forms
Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs
A Lossless Deamortization for Dynamic Greedy Set Cover
Quantum Computational Advantage with Constant-Temperature Gibbs Sampling
Which Crossing Number is it, Anyway?
Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs
The Complexity of 3-Colouring H-Colourable Graphs
A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Fault detecting experiments for sequential circuits
Balancing Vectors in Any Norm
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Representing Program Schemes in Logic
Smoothed Complexity of 2-player Nash Equilibria
Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems
Cascade synthesis of finite-state machines
Decision Problems for Propositional Linear Logic
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation
Genome Rearrangements and Sorting by Reversals
Depth-First Search and Linear Graph Algorithms (Working Paper)
Deux applications de la representation matricielle d'une serie rationnelle non commutative
A Parallel Approximation Algorithm for Positive Semidefinite Programming
Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation
Cryptography from Sunspots: How to Use an Imperfect Reference String
An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution
Structure in Locally Optimal Solutions (Extended Abstract)
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
A Simple and Approximately Optimal Mechanism for an Additive Buyer
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search
Time-Space Trade-Offs for General Recursion
Structure Learning of Hamiltonians from Real-Time Evolution
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions
Pseudorandom Generators in Propositional Proof Complexity
39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998
Two Decades of Temporal Logic: Achievements and Challenges (Abstract)
Playing Non-linear Games with Linear Oracles
Constant Depth Formula and Partial Function Versions of MCSP are Hard
Optimizing Star-Convex Functions
Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy
Multi-unit Auctions with Budget Limits
10th Annual Symposium on Switching and Automata Theory, Waterloo, Ontario, Canada, October 15-17, 1969
New Algorithms for the Disk Scheduling Problem
Alternating-time Temporal Logic
Measure on Small Complexity Classes, with Applications for BPP
On the Compressibility of NP Instances and Cryptographic Applications
Sparse Oracles and Uniform Complexity Classes
Number-theoretic Constructions of Efficient Pseudo-random Functions
How to Generate Cryptographically Strong Sequences of Pseudo Random Bits
Truthful Approximation Schemes for Single-Parameter Agents
Communication Complexity for Parallel Divide-and-Conquer
Fast Approximation Algorithms for Fractional Packing and Covering Problems
An Optimal Bound for Two Dimensional Bin Packing
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
The Complexity of Recognizing Polyhedral Scenes (Extended Abstract)
Binary Search Partitions for Fat Rectangles
Implication techniques for Boolean functions
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness
Orthogonal Range Reporting in Three and Higher Dimensions
Guaranteed Matrix Completion via Nonconvex Factorization
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings
The Theory of Joins in Relational Data Bases (Extended Abstract)
Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)
Competitive Analysis of Financial Games
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
A New Approach to Post-Quantum Non-Malleability
Potential of the Approximation Method (extended abstract)
Consistency of Synchronization Nets using P and V Operations
Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols
On Tape-Bounded Complexity Classes and Multi-Head Finite Automata
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Fast and Feasible Periodic Sorting Networks of Constant Depth
Minimax Rates for Robust Community Detection
Expander Codes
On Time versus Space and Related Problems
Probabilistic Analysis of Some Bin-Packing Problems
Threshold logic and two-person, zero-sum games
A Communication-Time Tradeoff
The Computability and Complexity of Optical Beam Tracing
Errata to "Atomic Shared Register Access by Asynchronous Hardware"
Approximation Algorithms for Submodular Multiway Partition
Description and Analysis of an Efficient Priority Queue Representation
Envy-Free Cake-Cutting for Four Agents
On Reversal Complexity for Alternating Turing Machines (Extended Abstract)
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization
Hardness of Approximating the Closest Vector Problem with Pre-Processing
Computing a Shortest k-Link Path in a Polygon
An Algorithmic Theory of Learning: Robust Concepts and Random Projection
A New Algorithm for Minimizing Convex Functions over Convex Sets (Extended Abstract)
Using Expander Graphs to Find Vertex Connectivity
Detecting a Network Failure