yusuke1997/dblp-id-title huggingface dataset:
The Unsolvability of the Equivalence Problem for epsilon-free NGSM's with Unary Input (Output) Alphabet and Applications
Optimal mixing of the down-up walk on independent sets of a given size
New Directions in Cryptography: Twenty Some Years Later
Network Synchronization with Polylogarithmic Overhead
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications
Non-Malleable Codes for Small-Depth Circuits
On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations
Approximate Constraint Satisfaction Requires Large LP Relaxations
Coding Theory: Tutorial and Survey
Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy
The Complexity of the Theory of p-adic Numbers
Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes
On the Diameter of Finite Groups
Learning with Errors in Answers to Membership Queries
Stochastic and Worst-Case Generalized Sorting Revisited
On the Complexity of a Game Related to the Dictionary Problem
Generating Random Spanning Trees
Designing Networks for Selfish Users is Hard
On the Power of Statistical Zero Knowledge
Decoding Turbo-Like Codes via Linear Programming
Counting and Cutting Cycles of Lines and Rods in Space
Optimal Algorithms for Parallel Polynomial Evaluation
On Learning Monotone Boolean Functions
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time
Error-Correcting Codes for Automatic Control
Reconsider the State Minimization Problem for Stochastic Finite State Systems
A Lower Bound for Dynamic Approximate Membership Data Structures
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders
How Easy Is Local Search? (Extended Abstract)
A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match
The Complexity of Acyclic Conjunctive Queries
Towards Instance-Optimal Euclidean Spanners
New Structures and Algorithms for Length-Constrained Expander Decompositions
Recommendation Systems: A Probabilistic Analysis
Local Hamiltonians Whose Ground States Are Hard to Approximate
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
An Old Linear Programming Algorithm Runs in Polynomial Time
Optimal Long Code Test with One Free Bit
Maximum Flow by Augmenting Paths in n 2+o(1) Time
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs
A Holant Dichotomy: Is the FKT Algorithm Universal?
Reduction of feedback loops in sequential circuits and carry leads in iterative networks
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
The shrinkage exponent is 2
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
On ACC
Partially ordered classes of finite automata
Faster Algorithms for Text-to-Pattern Hamming Distances
Geometric Retrieval Problems
Optimal Parallel Hull Construction for Simple Polygons in \calO(log log n) Time
Logconcave Functions: Geometry and Efficient Sampling Algorithms
Learning Noisy Perceptrons by a Perceptron in Polynomial Time
How to Construct Random Functions (Extended Abstract)
Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract)
Recursive Construction for 3-Regular Expanders
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
A Minimum Spanning Ellipse Algorithm
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract)
Any AND-OR Formula of Size N can be Evaluated in time N 1/2+o(1) on a Quantum Computer
FIXP-membership via Convex Optimization: Games, Cakes, and Markets
Secure Computation Meets Distributed Universal Optimality
The Uniform Halting Problem for Generalized One State Turing Machines
A Faster Distributed Single-Source Shortest Paths Algorithm
A Characterization of the (natural) Graph Properties Testable with One-Sided Error
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve
Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits
Dynamic Monotone Priorities on Planar Sets (Extended Abstract)
Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract)
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
Memory-Query Tradeoffs for Randomized Convex Optimization
Automatic fault detection in combinational switching networks
A flow chart notation for the description of a speed-independent control
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
Proving by Example and Gap Theorems
Genus g Graphs have Pagenumber O(sqrt(g))
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Resolution is Not Automatizable Unless W[P] is Tractable
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log
Flipping Persuasively in Constant Expected Time (Preliminary Version)
Partition of Planar Flow Networks (Preliminary Version)
Revisiting Agnostic PAC Learning
An Application of Coding Algebra to the Design of a Digital Multiplexing System using Linear Sequential Circuits
Inductive Inference: A Recursion Theoretic Approach
A Characterization of Multiclass Learnability
Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version)
Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average (Extended Abstract)
Security Preserving Amplification of Hardness
On the Relation of Graph Grammars and Graph Automata
Learning Linear Transformations
Statistically Near-Optimal Hypothesis Selection
The minimal canonical form of a tensor network
An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
The Complexity of Isomorphism Testing
Constructive Discrepancy Minimization for Convex Sets
Polynomial Learning of Distribution Families
Some Results on the Effect of Arithmetics on Comparison Problems
On the minimal third order expression of a Boolean function
A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects
Bounded Independence Fools Degree-2 Threshold Functions
Functional forms of majority functions and a necessary and sufficient condition for their realizability
Parallel Tree Contraction and Its Application
Finding separator cuts in planar graphs within twice the optimal
Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors
Communication-Space Tradeoffs for Unrestricted Protocols
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random
The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
Smoothed Analysis of Multiobjective Optimization
A New Parallel Algorithm for the Maximal Independent Set Problem
Sparse Random Linear Codes are Locally Decodable and Testable
The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms
On One-way Functions and Kolmogorov Complexity
Quantum Search of Spatial Regions
Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification
General Composition and Universal Composability in Secure Multi-Party Computation
A Proof of CSP Dichotomy Conjecture
On the Complexity of Space Bounded Interactive Proofs (Extended Abstract)
43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings
Some Formal Properties of a Class of Non-Deterministic Program Schemata
On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract)
High Level Languages of Maximum Power
Faster Sparse Minimum Cost Flow by Electrical Flow Localization
Scheduling with Communication Delays via LP Hierarchies and Clustering
The Intersection of Two Halfspaces Has High Threshold Degree
Threshold circuits of bounded depth
Generalised entropy accumulation
A general lower bound for mixing of single-site dynamics on graphs
Multi-Index Hashing for Information Retrieval
Lower Bounds for Natural Proof Systems
Efficient Statistics, in High Dimensions, from Truncated Samples
Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
Use of a list processing language in programming simplification procedures
Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)
Geometric Computation and the Art of Sampling
Finding Points on Curves over Finite Fields (Extended Abstract)
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
A Lattice Problem in Quantum NP
Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model
The Limits of Two-Party Differential Privacy
On the Movement of Robot Arms in 2-Dimensional Bounded Regions
37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14-16 October, 1996
An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games
Time-Space Tradeoffs for Undirected Graph Traversal
Sample-Optimal Fourier Sampling in Any Constant Dimension
Oracle-Efficient Online Learning and Auction Design
Local Privacy and Statistical Minimax Rates
Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
On the "log rank"-Conjecture in Communication Complexity
A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers
Efficient Implementation of Graph Algorithms Using Contraction
"Soft-decision" Decoding of Chinese Remainder Codes
Parallel Program Schemata: A Mathematical Model for Parallel Computation
Two Characterizations of the Context-Sensitive Languages
The Quantum Complexity of Set Membership
Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs
Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract)
First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
Polynomial-Time Power-Sum Decomposition of Polynomials
30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua
Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions
Parallel Algorithms for Higher-Dimensional Convex Hulls
On the Complexity of Many Faces in Arrangements of Circles
2D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
Frugal Mechanism Design via Spectral Techniques
Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract)
Subcubic Equivalences between Path, Matrix and Triangle Problems
Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model
Logics for Reasoning about Cryptographic Constructions
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
Propositional Game Logic
Controlling Concurrency Using Locking Protocols (Preliminary Report)
A Faster Isomorphism Test for Graphs of Small Degree
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple
Improved Parallel Polynomial Division and Its Extensions
Fooling polynomials using invariant theory *
On Choosing a Dense Subgraph (Extended Abstract)
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design
A Spectral Algorithm for Learning Mixtures of Distributions
A Randomized Rounding Approach to the Traveling Salesman Problem
Faster high-accuracy log-concave sampling via algorithmic warm starts
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF
A Fast Algorithm for the Elimination of Common Subexpressions
Total Space in Resolution
Extracting Randomness from Samplable Distributions
An Information Statistics Approach to Data Stream and Communication Complexity
An Unconditional Study of Computational Zero Knowledge
On the (Im)possibility of Cryptography with Imperfect Randomness
Randomized and deterministic algorithms for geometric spanners of small diameter
Power Series Composition in Near-Linear Time
An O(n log ^3 n) Algorithm for the Real Root Problem
Concurrent Reachability Games
Semidefinite Relaxations for Parallel Machine Scheduling
Parallel Repetition for the GHZ Game: Exponential Decay
Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
Algorithms to Tile the Infinite Grid with Finite Clusters
26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985
The Number of Solutions for Random Regular NAE-SAT
Is it Easier to Prove Theorems that are Guaranteed to be True?
Incidences between Points and Lines in R^4
On Range Searching in the Group Model and Combinatorial Discrepancy
On the Cunning Power of Cheating Verifiers: Some Observations about Zero Knowledge Proofs (Extended Abstract)
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Implicit Data Structures for the Weighted Dictionary Problem (preliminary version)
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023
Optimal File Sharing in Distributed Networks (Preliminary Version)
A Better Lower Bound for Quantum Algorithms Searching an Ordered List
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
A Parallel Algorithm for Finding a Separator in Planar Graphs
Approximation Algorithms for Orienteering and Discounted-Reward TSP
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
Correct Computation Rules for Recursive Languages (Extended Abstract)
Dimension Reduction in the \ell _1 Norm
Spectral Graph Theory and its Applications
On the Power of Multiplication in Random Access Machines
On the Minimal Synchronism Needed for Distributed Consensus
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
Competitive Snoopy Caching
A Polynomial Solution for Potato-peeling and other Polygon Inclusion and Enclosure Problems
Rational Protocol Design: Cryptography against Incentive-Driven Adversaries
15th Annual Symposium on Switching and Automata Theory, New Orleans, Louisiana, USA, October 14-16, 1974
An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
A Mildly Exponential Approximation Algorithm for the Permanent
Much Faster Algorithms for Matrix Scaling
22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981
An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)
On the Homotopy Test on Surfaces
On the Direct Sum Conjecture (Extended Summary)
Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version)
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Simulating BPP Using a General Weak Random Source
FO Model Checking on Posets of Bounded Width
Isomorphism Testing for Graphs Excluding Small Minors
Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract)
Heavy-Tailed Independent Component Analysis
Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Noise stability of functions with low in.uences invariance and optimality
The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree
Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies
Approximation Algorithms for Euler Genus and Related Problems
Optimal mixing for two-state anti-ferromagnetic spin systems
Gossip-Based Computation of Aggregate Information
Query Incentive Networks
The Distance Bound for Sorting on Mesh-Connected Processor Arrays Is Tight (Preliminary Report)
A New Approach for Testing Properties of Discrete Distributions
IOPs with Inverse Polynomial Soundness Error
Program Equivalence and Context-Free Grammars
The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs
Linearity Testing in Characteristic Two
On the Existence of Pseudorandom Generators (Extended Abstract)
How Powerful is Adiabatic Quantum Computation?
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits
Polynomial Time Approximation Schemes for Geometric k-Clustering
A Parallel Repetition Theorem for Any Interactive Argument
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
Testing Assignments to Constraint Satisfaction Problems
Slicing all Edges of an n-cube Requires n 2/3 Hyperplanes
An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads (Extended Abstract)
Stochastic Optimization is (Almost) as easy as Deterministic Optimization
Pseudorandomness for Read-Once Formulas
On Range Searching with Semialgebraic Sets II
On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata
Tensor Cumulants for Statistical Inference on Invariant Distributions
A Lower Bound for Probabilistic Algorithms for Finite State Machines
Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums
Linear-time Recognition of Circular-arc Graphs
Learning Binary Relations and Total Orders (Extended Abstract)
Single Source - All Sinks Max Flows in Planar Digraphs
Series-Parallel Irreducibility: Machine Oriented Definitions and Proofs
Efficient Testing of Large Graphs
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields
A Fast and Simple Unbiased Estimator for Network (Un)reliability
A Counter-example to Karlin's Strong Conjecture for Fictitious Play
A Markovian Extension of Valiant's Learning Model (Extended Abstract)
The Complexity of Rationalizing Network Formation
"Planar" Tautologies Hard for Resolution
Verifying Identities (extended abstract)
Locally Testable Cyclic Codes
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Minimum Partition of Polygonal Regions into Trapezoids
Buy-at-Bulk Network Design
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms
Input Sparsity and Hardness for Robust Subspace Approximation
Applying Static Network Protocols to Dynamic Networks
On the Modular Decomposition of Autonomous Sequential Machines
Understanding Incentives: Mechanism Design Becomes Algorithm Design
Robin Hood Hashing (Preliminary Report)
The Ising Model on Trees: Boundary Conditions and Mixing Time
An Algorithmic Approach to the Automated Design of Parts Orienters
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data
The Recursive Equivalence of the Reachability Problem and the Liveness Problem for Petri Nets and Vector Addition Systems
Decidability of Equivalence, Containment, Intersection, and Separability of Context-Free Languages (Extended Abstract)
Parameterized Proof Complexity
A Polynomial Algorithm for Recognizing Perfect Graphs
Making the Most of Advice: New Correlation Breakers and Their Applications
Faster Exact and Approximate Algorithms for k-Cut
A Tight Characterization of NP with 3 Query PCPs
The Efficient Calculation of Powers of Polynomials
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings
Matching Vector Codes
The Power of Geometric Duality
Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids
Coloring Inductive Graphs On-Line
Tight Bounds on the Complexity of Cascaded Decomposition of Automata
A 5/2 n 2 -Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
Low Contention Linearizable Counting
KRW Composition Theorems via Lifting
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract)
Online Matching with Stochastic Rewards
Bridge Girth: A Unifying Notion in Network Design
Why are Proof Complexity Lower Bounds Hard?
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Approximability and in-approximability results for no-wait shop scheduling
Query-to-Communication Lifting for BPP
41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, 2000
Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Faster Deterministic Sorting and Searching in Linear Space
Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems
Lower Bounds for Additive Spanners, Emulators, and More
Approximate Max Flow on Small Depth Networks
On Symmetric Factorizations of Hankel Matrices
Information Equals Amortized Communication
Time Bounds on Space Computations
The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant
The Power of Parallelism for Automatic Program Synthesis
Quantum Expander Codes
Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Realization of Stochastic Systems
Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract)
Hashing for Statistics over K-Partitions
Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
Recognition of Context-Free and Stack Languages
Dynamically Computing the Maxima of Decomposable Functions, with Applications
A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures
Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
On the Program Size of Perfect and Universal Hash Functions
An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs
On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract)
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization
An Approximate Generalization of the Okamura-Seymour Theorem
40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999
Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract)
A linear-processor polylog-time algorithm for shortest paths in planar graphs
Graphs of Affine Transformations, with Applications to Sequential Circuits
Algebraic Structures and Algorithms for Matching and Matroid Problems