yusuke1997/dblp-id-title huggingface dataset:
Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds
Effectively Polynomial Simulations
Learning Versus Pseudorandom Generators in Constant Parallel Time
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
An Axiomatic Study of Scoring Rule Markets
Smooth and Strong PCPs
A VLSI Circuit Model Accounting for Wire Delay
On the Size Overhead of Pairwise Spanners
Computationally Data-Independent Memory Hard Functions
Simplicial Covering Dimension of Extremal Concept Classes
Adversary lower bound for the k-sum problem
On the Download Rate of Homomorphic Secret Sharing
Quantum Meets the Minimum Circuit Size Problem
Nearest Neighbor Complexity and Boolean Circuits
Beyond Worst-Case Budget-Feasible Mechanism Design
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems
A Combinatorial Approach to Robust PCA
Reachability in graph timelines
How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts
On the Impossibility of Probabilistic Proofs in Relativized Worlds
Learning mixtures of arbitrary distributions over large discrete domains
Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
Quantum strategic game theory
Uniform Sampling for Matrix Approximation
Polynomials, Divided Differences, and Codes
Robust device independent quantum key distribution
Quantum interactive proofs with weak error bounds
Analyzing the Economic Impact of Decentralization on Users
Simultaneously Load Balancing for Every p-norm, With Reassignments
Trade-Offs Between Size and Degree in Polynomial Calculus
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
Spanning Adjacency Oracles in Sublinear Time
The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games
How To Bootstrap Anonymous Communication
A Computational Separation Between Quantum No-Cloning and No-Telegraphing
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H
Improved Rate for Non-Malleable Codes and Time-Lock Puzzles
PPP-Completeness and Extremal Combinatorics
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Information Complexity Density and Simulation of Protocols
Data-Driven Solution Portfolios
The Space Complexity of Sampling
Exponential Separations Using Guarded Extension Variables
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity
Sampling Correctors
Sparse extractor families for all the entropy
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Space-bounded communication complexity
Dynamic Maximal Matching in Clique Networks
Signed Tropical Convexity
The Learning Stabilizers with Noise Problem
Testing Local Properties of Arrays
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free
Quantum Advantage and Lower Bounds in Parallel Query Complexity
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
Pipeline Interventions
Data Reconstruction: When You See It and When You Don't
New affine-invariant codes from lifting
On Sketching Quadratic Forms
Certificate Games
Simulating Noisy Channel Interaction
Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices
Rational Proofs with Multiple Provers
Condorcet-Consistent and Approximately Strategyproof Tournament Rules
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs
Sherali-Adams relaxations and indistinguishability in counting logics
Pricing Loss Leaders can be Hard
Span Programs and Quantum Space Complexity
Monotone Complexity of Spanning Tree Polynomial Re-Visited
Determinants vs. Algebraic Branching Programs
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)
Smaller ACC0 Circuits for Symmetric Functions
On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]
Welfare maximization and the supermodular degree
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)
Robust Perfect Revenue From Perfectly Informed Players
A Spectral Approach to Polytope Diameter
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract)
Recovering Communities in Structured Random Graphs
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Accuracy for Sale: Aggregating Data with a Variance Constraint
Resource-based corruptions and the combinatorics of hidden diversity
On the Construction of One-Way Functions from Average Case Hardness
Characterizing the sample complexity of private learners
Fractal Structures in Adversarial Prediction
Dynamic Models of Reputation and Competition in Job-Market Matching
Loss Minimization Yields Multicalibration for Large Neural Networks
Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians
Algorithmic Persuasion with Evidence
Loss Minimization Through the Lens Of Outcome Indistinguishability
Optimal Deterministic Clock Auctions and Beyond
The Space-Time Cost of Purifying Quantum Computations
The Variable-Processor Cup Game
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Communication Complexity of Inner Product in Symmetric Normed Spaces
Lifting with Sunflowers
Expander Decomposition in Dynamic Streams
Quantum Algorithms and the Power of Forgetting
Local Algorithms for Block Models with Side Information
Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage
Sum of Squares Lower Bounds from Symmetry and a Good Story
Proofs of Quantumness from Trapdoor Permutations
Computing Exact Minimum Cuts Without Knowing the Graph
Property Testing via Set-Theoretic Operations
Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach
Maximizing Miner Revenue in Transaction Fee Mechanism Design
Towards a Unified Complexity Theory of Total Functions
Non-commutative arithmetic circuits with division
Communication Memento: Memoryless Communication Complexity
Memory Consistency Conditions for Self-Assembly Programming
Learning mixtures of spherical gaussians: moment methods and spectral decompositions
Optimal provision-after-wait in healthcare
Towards Human Computable Passwords
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?
On a Natural Dynamics for Linear Programming
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
Asynchronous Multi-Party Quantum Computation
8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, USA, January 9-11, 2017
Barriers for Rank Methods in Arithmetic Complexity
Fractional Certificates for Bounded Functions
Towards Hardness of Approximation for Polynomial Time Problems
Limits for Rumor Spreading in Stochastic Populations
Advancing Subgroup Fairness via Sleeping Experts
The Effects of Diversity in Aggregation Games
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
Hierarchical Functional Encryption
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
Non-Negative Sparse Regression and Column Subset Selection with L1 Error
It'll Probably Work Out: Improved List-Decoding Through Random Operations
Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
Multi-Clique-Width
Distribution Testing with a Confused Collector
Vertex Sparsification for Edge Connectivity in Polynomial Time
Secure Distributed Network Optimization Against Eavesdroppers
Publicly verifiable proofs of sequential work
Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
Cubic Formula Size Lower Bounds Based on Compositions with Majority
Adversarial Leakage in Games
Efficient Testing without Efficient Regularity
Two-State Spin Systems with Negative Interactions
A New Connection Between Node and Edge Depth Robust Graphs
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory
On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement
How to Incentivize Data-Driven Collaboration Among Competing Parties
Algorithmic Polarization for Hidden Markov Models
On Flipping the Fréchet Distance
Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions
The Classification of Reversible Bit Operations
Sample-Based Proofs of Proximity
Identity Testing for Circuits with Exponentiation Gates
On the power of conditional samples in distribution testing
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Distance-Preserving Graph Contractions
Self-Sustaining Iterated Learning
Tensor Network Complexity of Multilinear Maps
Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times
Differential Privacy on Finite Computers
Unconditional Pseudorandomness Against Shallow Quantum Circuits
The garden-hose model
Secret Sharing, Slice Formulas, and Monotone Real Circuits
Low Sensitivity Hopsets
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
Strategic Classification
On Oblivious Amplification of Coin-Tossing Protocols
Bounds on locally testable codes with unique tests
Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
Interactive Proofs for Distribution Testing with Conditional Oracles
Samplability Makes Learning Easier
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
Recovery from Non-Decomposable Distance Oracles
Multicommodity flows and cuts in polymatroidal networks
A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions
Making Progress Based on False Discoveries
Consensus vs Broadcast, with and Without Noise (Extended Abstract)
Real Stability Testing
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2)
Keep That Card in Mind: Card Guessing with Limited Memory
Obfuscating Conjunctions under Entropic Ring LWE
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees
Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)
Separators in Region Intersection Graphs
Online Pen Testing
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Compression in a Distributed Setting
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions
Average Sensitivity of Geometric Algorithms
Dynamic Inference in Probabilistic Graphical Models
Best-Response Mechanisms
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard
Capacity of non-malleable codes
On Semi-Algebraic Proofs and Algorithms
Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization
A Complete Characterization of Unitary Quantum Space
Evasiveness through a circuit lens
Fully Characterizing Lossy Catalytic Computation
On the automorphism groups of strongly regular graphs I
Excluding PH Pessiland
Quantum Money from Abelian Group Actions
Algebraic Restriction Codes and Their Applications
Information Design with Unknown Prior (Extended Abstract)
Rigidity for Monogamy-Of-Entanglement Games
Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
New Greedy Spanners and Applications
Balanced Allocations with Incomplete Information: The Power of Two Queries
Differentially Oblivious Turing Machines
Incompressible Functional Encryption
Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu
Stable Matching with Interviews
Toward Separating QMA from QCMA with a Classical Oracle
Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015
Posting Prices with Unknown Distributions
Beyond Natural Proofs: Hardness Magnification and Locality
The Randomness Complexity of Differential Privacy
Small Circuits Imply Efficient Arthur-Merlin Protocols
Partial Minimum Branching Program Size Problem Is ETH-Hard
Learning Dynamics and the Co-Evolution of Competing Sexual Species
Limits to Non-Malleability
Fixed-Parameter Tractable Submodular Maximization over a Matroid
Sampling, Flowers and Communication
On the PTAS Complexity of Multidimensional Knapsack
Uniform Bounds for Scheduling with Job Size Estimates
The Subgraph Testing Model
17th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026
Testing monotonicity of distributions over general partial orders
A New Approach to the Sensitivity Conjecture
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints
Almost Envy-Free Allocations with Connected Bundles
Polynomial Size, Short-Circuit Resilient Circuits for NC
Classical Verification of Quantum Learning
Omnipredictors
Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
Edge-Minimum Walk of Modular Length in Polynomial Time
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election
On the Computational Complexity of Optimal Simple Mechanisms
Finite Sample Differentially Private Confidence Intervals
SOS Lower Bounds with Hard Constraints: Think Global, Act Local
Better Outcomes from More Rationality
Online Versus Offline Adversaries in Property Testing
Efficiently Testable Circuits
Energy-efficient circuit design
Limits of local algorithms over sparse random graphs
Bounding Rationality by Discounting Time
Adversarially Robust Property-Preserving Hash Functions
Circuit Depth Reductions
The Computational Cost of Asynchronous Neural Communication
Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior
Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space
Runtime guarantees for regression problems
Secret Sharing with Binary Shares
Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers
Robust Hierarchical k-Center Clustering
Estimating Euclidean Distance to Linearity
Sparsity Lower Bounds for Probabilistic Polynomials
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle
Cryptogenography
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage
Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions
Local Access to Huge Random Objects Through Partial Sampling
Metrical Service Systems with Transformations
Paging for multi-core shared caches
Adjacency Labeling Schemes for Small Classes
Making Auctions Robust to Aftermarkets
Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting
Is Untrusted Randomness Helpful?
Multi-Channel Bayesian Persuasion
Recursive Error Reduction for Regular Branching Programs
Pseudobinomiality of the Sticky Random Walk
Selection Problems in the Presence of Implicit Bias
Triangle Detection in H-Free Graphs
The curse of simultaneity
Correlation Detection in Trees for Planted Graph Alignment
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP
Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods
Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
On the (In)approximability of Combinatorial Contracts
Leaky Pseudo-Entropy Functions
On Sample-Based Testers
Homogeneous Algebraic Complexity Theory and Algebraic Formulas
Ad Hoc Multi-Input Functional Encryption
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
Decision-Making Under Miscalibration
Competing provers protocols for circuit evaluation
Explicit Abelian Lifts and Quantum LDPC Codes
Algorithms with More Granular Differential Privacy Guarantees
Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length
Bounds on the Quantum Satisfiability Threshold
Classical and Quantum Polynomial Freiman-Ruzsa Algorithms
A characterization of approximation resistance for even k-partite CSPs
Support Recovery in Universal One-Bit Compressed Sensing
Low-Sensitivity Functions from Unambiguous Certificates
Comparison Graphs: A Unified Method for Uniformity Testing
(Leveled) fully homomorphic encryption without bootstrapping
Circular Trace Reconstruction
Pseudorandomness and the Minimum Circuit Size Problem
Black-Box Uselessness: Composing Separations in Cryptography
A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games
The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
Bosonic Quantum Computational Complexity
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
Maximizing Revenue in the Presence of Intermediaries
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
Equivocal Blends: Prior Independent Lower Bounds
Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure
Optimal Single-Choice Prophet Inequalities from Samples
Conditional Sparse Linear Regression
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Accumulation Without Homomorphism
Matroid Partition Property and the Secretary Problem
Limits of random oracles in secure computation
Interactive Proofs for Verifying Machine Learning
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
Approaching utopia: strong truthfulness and externality-resistant mechanisms
Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
Consensus Division in an Arbitrary Ratio
Inferential Privacy Guarantees for Differentially Private Mechanisms
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data
An Improved Protocol for ExactlyN with More Than 3 Players
Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions)
Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs
The Complexity of Infinite-Horizon General-Sum Stochastic Games
Locally Private Histograms in All Privacy Regimes
An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem
Towards an optimal query efficient PCP?
The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach
Online Learning and Bandits with Queried Hints
Practical verified computation with streaming interactive proofs
Online Search with a Hint
Distribution-Specific Agnostic Boosting
Space-Efficient Estimation of Robust Statistics and Distribution Testing
"Quantum Supremacy" and the Complexity of Random Circuit Sampling
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract)
Proof-Carrying Data and Hearsay Arguments from Signature Cards
Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound
Low-weight halfspaces for sparse boolean vectors
Efficient Control of Temporal Reasoning
A Deductive Decision Procedure for a Restricted FTL
Theorem Proving for Temporal Logics of Knowledge or Belief
Automatic Generation of Implied Constraints: Project Description
Propositional Temporal Resolution Revised
A Decision Procedure for Term Algebras with Queues
Congruence Classes with Logic Variables
Description Logics and Knowledge Discovery of Data
Automata on Infinite Words and Temporal Logic Normal Forms
Application of Simplification Theories
Computer Algebra and Automated Reasoning
Hyperresolution for Guarded Formulae
Finite Model Building for Propositional Gödel-Logics as an Example for Projective Logics
Proceedings of the Seventh Workshop on Automated Reasoning, Bridging the Gap between Theory and Practice, King's College London, UK, 20-21 July 2000
The Existential Theories of Term Algebras with the Knuth-Bendix Orderings are Decidable
The Description Logic Reasoner CICLOP (Version 2.0)
Practical Proof Methods for Combined Modal and Temporal Logics
Exclusion of Symmetries in Search - A Spin-off from Bioinformatics Research
Modal Experiments
Automatic Generation of Concurrent Provers
Run-time Optimisations for Reasoning with Intensional Logics
Deciding Fluted Logic with Resolution
Using Deduction Techniques for Natural Language Understanding
Reasoning in Description Logics with Wellington 1.0 - System Description
Resource Guided Concurrent Deduction
Towards Automating Inductive Proofs for State Monads
Goal Directed Mechanisms: Proofs, Interpolation and Abduction Procedures
Forward and Backward Chaining in Linear Logic
System Description: Vampire 1.0
A Deadlock-Free Solution for Multi-Agent Pickup and Delivery in Presence of External Agents
Deconvolutional networks for point-cloud vehicle detection and tracking in driving scenarios
Enhancing Lidar Point Cloud Sampling via Colorization and Super-Resolution of Lidar Imagery
Contact sensing and mobility in rough and cluttered environments
Understanding Greediness in Map-Predictive Exploration Planning
Evaluation of the Robot Sign Language Tutoring Assistant using Video-based Studies
Rapid free-space mapping from a single omnidirectional camera
Odometry Enhancement and Localization in Orchards Using Tree Trunk Landmarks with 2D LiDAR
Social APF-RL: Safe Mapless Navigation in Unknown & Human-Populated Environments
Towards Life-Long Autonomy of Mobile Robots Through Feature-Based Change Detection
Grasping on the move: A generic arm-base coordinated grasping pipeline for mobile manipulation
Comparison of shape matching techniques for place recognition
Motion Planning for Multi-Legged Robots Using Levenberg-Marquardt Optimization with Bézier Parametrization
Mobile Robot Environment Perception: Adaptable Real-Time Neural Network Architecture for RGB-D Ground Segmentation *
Mapping the Static Parts of Dynamic Scenes from 3D LiDAR Point Clouds Exploiting Ground Segmentation
Plant Detection and Mapping for Agricultural Robots using a 3D-lidar Sensor
Efficient extensible path planning on 3D terrain using behavior modules
Revisiting Distribution-Based Registration Methods