yusuke1997/dblp-id-title huggingface dataset:
On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting
Multiplicative updates in coordination games and the theory of evolution
Interactive Proofs For Quantum Computations
The Strongish Planted Clique Hypothesis and Its Consequences
Matroid Secretary Is Equivalent to Contention Resolution
Noise vs computational intractability in dynamics
Quantum Versus Randomized Communication Complexity, with Efficient Players
Pseudodeterministic Algorithms for Minimum Cut Problems
Bayesian Perspective on Memorization and Reconstruction
Robustly Leveraging Collusion in Combinatorial Auctions
A Log-Sobolev Inequality for the Multislice, with Applications
Entry-Specific Matrix Estimation Under Arbitrary Sampling Patterns Through the Lens of Network Flows (Extended Abstract)
Parameterized Geometric Graph Modification with Disk Scaling
Total NP Search Problems with Abundant Solutions
Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras
FPT Approximation for Capacitated Sum of Radii
Succinct Fermion Data Structures
Beating the Folklore Algorithm for Dynamic Matching
Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
Facility Location on High-Dimensional Euclidean Spaces
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes
Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete
Weighted Chairman Assignment and Flow-Time Scheduling
Quantum Majority Vote
Supercritical Tradeoff Between Size and Depth for Resolution over Parities
Complex Contagions in Kleinberg's Small World Model
MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence
Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality
Catalytic Communication
Renegotiation-Safe Protocols
Direct Sum Testing
Adaptive Massively Parallel Constant-Round Tree Contraction
Auction Revenue in the General Spiteful-Utility Model
An efficient algorithm for finding the ground state of 1D gapped local hamiltonians
Towards Stronger Depth Lower Bounds
Quickly Determining Who Won an Election
A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits
Range Longest Increasing Subsequence and Its Relatives
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
Interactive Coding for Multiparty Protocols
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
Incentive Compatible Active Learning
Convex Influences
Submodular Secretary Problem with Shortlists
Single-Round Proofs of Quantumness from Knowledge Assumptions
Parameterized Property Testing of Functions
Learnability of DNF with representation-specific queries
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Lattice-based FHE as secure as PKE
On Interactive Proofs of Proximity with Proof-Oblivious Queries
Conditional Hardness for Sensitivity Problems
Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
Locally testable codes and cayley graphs
Dimension-Free Correlated Sampling for the Hypersimplex
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds
Unitary Property Testing Lower Bounds by Polynomials
Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids
Geometric Covering via Extraction Theorem
Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions
Sequential Defaulting in Financial Networks
Oracle Separations for the Quantum-Classical Polynomial Hierarchy
Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
Choice and Bias in Random Walks
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces
Communication with Imperfectly Shared Randomness
Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem
Kronecker Powers of Tensors and Strassen's Laser Method
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)
Self-Testing of a Single Quantum Device Under Computational Assumptions
Distribution Design
On the Space Complexity of Linear Programming with Preprocessing
A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates
Expander Construction in VNC1
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
On the Communication Complexity of Secure Function Evaluation with Long Output
Private Counting of Distinct and k-Occurring Items in Time Windows
Online Paging with a Vanishing Regret
New Pseudorandom Generators and Correlation Bounds Using Extractors
A New Approach to Multi-Party Peer-to-Peer Communication Complexity
The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture (Extended Abstract)
Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms
Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
Competing Bandits: Learning Under Competition
The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract)
Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024
An equational approach to secure multi-party computation
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
Making evolution rigorous: the error threshold
Iterated group products and leakage resilience against NC1
Welfare maximization and truthfulness in mechanism design with ordinal preferences
Non-Malleable Codes
Streaming computations with a loquacious prover
Towards deterministic tree code constructions
Identity Check Problem for Shallow Quantum Circuits
13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, January 31 - February 3, 2022
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two
12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, January 6-8, 2021
Detecting communities is Hard (And Counting Them is Even Harder)
The Complexity of User Retention
Small Hazard-Free Transducers
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means
A New Look at Selfish Routing
Reducing Inefficiency in Carbon Auctions with Imperfect Competition
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations
Differential Privacy from Axioms
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
Geometric Bounds on the Fastest Mixing Markov Chain
On the Cryptographic Hardness of Local Search
Simple Verifiable Delay Functions
Higher-Order Delsarte Dual LPs: Lifting, Constructions and Completeness
Range Avoidance and Remote Point: New Algorithms and Hardness
Making Asynchronous Distributed Computations Robust to Channel Noise
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Algorithms and Adaptivity Gaps for Stochastic k-TSP
Crowdsourced Bayesian auctions
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
Cycle Detection, Order Finding and Discrete Log with Jumps
Massive online teaching to bounded learners
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation
Generalized List Decoding
Derandomized Squaring: An Analytical Insight into Its True Behavior
Fisher Zeros and Correlation Decay in the Ising Model
Improved Monotonicity Testers via Hypercube Embeddings
Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice
Differentially Private Approximate Pattern Matching
Candidate weak pseudorandom functions in AC 0 ○ MOD 2
Sketching Cuts in Graphs and Hypergraphs
Nonlinear Repair Schemes of Reed-Solomon Codes
Multiplayer Parallel Repetition for Expanding Games
Instance Complexity and Unlabeled Certificates in the Decision Tree Model
Restriction access
OV Graphs Are (Probably) Hard Instances
Why do simple algorithms for triangle enumeration work in the real world?
On the structure of boolean functions with small spectral norm
Downward Self-Reducibility in TFNP
Constant-Depth Sorting Networks
High Dimensional Random Walks and Colorful Expansion
Formulations and Constructions of Remote State Preparation with Verifiability, with Applications
Minimum Circuit Size, Graph Isomorphism, and Related Problems
The Time Complexity of Consensus Under Oblivious Message Adversaries
Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics [Working Paper Abstract]
On Rich 2-to-1 Games
Lifting to Parity Decision Trees via Stifling
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
Online Multivalid Learning: Means, Moments, and Prediction Intervals
Making Decisions Under Outcome Performativity
Deterministic Extractors for Additive Sources: Extended Abstract
A Universal Sequence of Tensors for the Asymptotic Rank Conjecture
Mechanism design with approximate valuations
A Combinatorial Characterization of Constant Mixing Time
Quantum Recommendation Systems
Necessary Conditions in Multi-Server Differential Privacy
Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!
A Hierarchy Theorem for Interactive Proofs of Proximity
Testers and their applications
TFNP Characterizations of Proof Systems and Monotone Circuits
Linear time decoding of regular expander codes
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Separation between Estimation and Approximation
Online Balanced Allocation of Dynamic Components
Deterministic compression with uncertain priors
Global Alignment of Molecular Sequences via Ancestral State Reconstruction
Forrelation Is Extremally Hard
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Majorizing Measures for the Optimizer
On Approximating the f-Divergence Between Two Ising Models
Approximating Approximate Distance Oracles
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography
Attribute-efficient evolvability of linear functions
Generalized Private Selection and Testing with High Confidence
Towards Local Testability for Quantum Coding
Communicating with Anecdotes (Extended Abstract)
Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive
Ideal Private Simultaneous Messages Schemes and Their Applications
Approximate Clustering with Same-Cluster Queries
A Generalized Matching Reconfiguration Problem
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization
What Can Cryptography Do for Decentralized Mechanism Design?
Parameterized testability
Certification with an NP Oracle
Stronger methods of making quantum interactive proofs perfectly complete
The Computational Benefit of Correlated Instances
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False
Scheduling with Predictions and the Price of Misprediction
Robustness of the Learning with Errors Assumption
Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?
Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium
Deterministic Dynamic Matching in Worst-Case Update Time
Lower Bounds for (Non-Monotone) Comparator Circuits
Computation over the Noisy Broadcast Channel with Malicious Parties
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions
Dynamics of prisoner's dilemma and the evolution of cooperation on networks
How to Sell Information Optimally: An Algorithmic Study
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
A New Approximation Technique for Resource-Allocation Problems
The Space Complexity of Mirror Games
List Agreement Expansion from Coboundary Expansion
Pan-Private Streaming Algorithms
Testing Classical Properties from Quantum Data
Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract)
Random Walks in Polytopes and Negative Dependence
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications
Interactive Communication in Bilateral Trade
Beating Classical Impossibility of Position Verification
Sublinear-Time Computation in the Presence of Online Erasures
FPT Algorithms for Finding Near-Cliques in c-Closed Graphs
Query Lower Bounds for Correlation Clustering Under Memory Constraints
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds
Almost-Orthogonal Bases for Inner Product Polynomials
Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More
Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks
The Complexity of DNF of Parities
Model-Generic Incrementally Verifiable Computation from Updatable BARGs
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
Error Correcting Codes for Uncompressed Messages
Error-Correcting Graph Codes
Symmetric Sparse Boolean Matrix Factorization and Applications
Arithmetic Cryptography: Extended Abstract
Testing Distributions of Huge Objects
On Disperser/Lifting Properties of the Index and Inner-Product Functions
Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
On Local Testability in the Non-Signaling Setting
Robust Algorithms for the Secretary Problem
Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation
Testing Linear Inequalities of Subgraph Statistics
Satisfiability on Mixed Instances
Quantum money from knots
Invitation games and the price of stability
Unconditional Quantum Advantage for Sampling with Shallow Circuits
Decentralized Data Archival: New Definitions and Constructions
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications
Zero-Knowledge Proofs of Proximity
Local-To-Global Agreement Expansion via the Variance Method
TFNP Intersections Through the Lens of Feasible Disjunction
Local Algorithms for Finding Interesting Individuals in Large Networks
Mixing of 3-Term Progressions in Quasirandom Groups
No justified complaints: on fair sharing of multiple resources
Query Complexity of Stochastic Minimum Vertex Cover
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations
Is This Correct? Let's Check!
Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH
An energy complexity model for algorithms
On Integer Programming and Convolution
Bootstrapping Homomorphic Encryption via Functional Encryption
Universal Communication, Universal Graphs, and Graph Labeling
One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity
Time-Lock Puzzles from Randomized Encodings
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
The Hardness of Learning Quantum Circuits and Its Cryptographic Applications
Finding Skewed Subcubes Under a Distribution
Graph Clustering using Effective Resistance
Sensitivity Analysis of the Maximum Matching Problem
Strategies for Quantum Races
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
A Complete Linear Programming Hierarchy for Linear Codes
Testing k-Monotonicity
Random Unitaries in Constant (Quantum) Time
Distribution-Free Testing of Linear Functions on ℝⁿ
Restricted Distribution Automatizability in PAC-Semantics
Advanced Composition Theorems for Differential Obliviousness
Differential Privacy and Sublinear Time Are Incompatible Sometimes
Random Projection in the Brain and Computation with Assemblies of Neurons
Strategyproof Scheduling with Predictions
Fully Succinct Garbled RAM
Cumulative Space in Black-White Pebbling and Resolution
Every Set in P Is Strongly Testable Under a Suitable Encoding
Commuting Local Hamiltonians Beyond 2D
On Generalized Corners and Matrix Multiplication
Robust Restaking Networks
Density Estimation for Shift-Invariant Multidimensional Distributions
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
Sorting noisy data with partial information
Hard Instances for Satisfiability and Quasi-one-way Functions
Expanders with respect to Hadamard spaces and random graphs: extended abstract
Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013
On the degree of univariate polynomials over the integers
Multireference alignment using semidefinite programming
Improved Hardness of BDD and SVP Under Gap-(S)ETH
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
Linear Matroid Intersection Is in Catalytic Logspace
Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes
On Locality-Sensitive Orderings and Their Applications
The Distortion of Locality Sensitive Hashing
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract)
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
A Quasi-Random Approach to Matrix Spectral Analysis
Correlation-Intractable Hash Functions via Shift-Hiding
Slice Rank and Partition Rank of the Determinant
Coresets for 1-Center in 𝓁₁ Metrics
Testing Submodularity and Other Properties of Valuation Functions
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract
Shallow circuits with high-powered inputs
Distributional PAC-Learning from Nisan's Natural Proofs
Relaxed Locally Correctable Codes
On Multiplicative Weight Updates for Concave and Submodular Function Maximization
Listing 6-Cycles in Sparse Graphs
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
DEEP-FRI: Sampling Outside the Box Improves Soundness
Lattice-based Locality Sensitive Hashing is Optimal
Markov Chain Robustness
Secure Multiparty Computation with General Interaction Patterns
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
The computational hardness of pricing compound options
Low Diameter Graph Decompositions by Approximate Distance Computation
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Equivalence of Systematic Linear Data Structures and Matrix Rigidity
Polynomial Identity Testing via Evaluation of Rational Functions
Low-Complexity Cryptographic Hash Functions
Fourier Sparsity of Delta Functions and Matching Vector PIRs
Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
Quantum rejection sampling
Improved Decoding of Expander Codes
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
Distributed Load Balancing: A New Framework and Improved Guarantees
Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election
Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs
Strategy-Stealing Is Non-Constructive
Faster private release of marginals on small databases
Algorithms and Hardness for Multidimensional Range Updates and Queries
Learning hurdles for sleeping experts
Game Efficiency Through Linear Programming Duality
Computationally Limited Randomness
More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks
16th Innovations in Theoretical Computer Science Conference, ITCS 2025, Columbia University, New York, NY, USA, January 7-10, 2025
Pseudorandom Self-Reductions for NP-Complete Problems
A Simple and Robust Protocol for Distributed Counting
Scheduling with Explorable Uncertainty
Toward a Theory of Markov Influence Systems and their Renormalization
Is privacy compatible with truthfulness?
Expander-Based Cryptography Meets Natural Proofs
A Schur Complement Cheeger Inequality
Hard Properties with (Very) Short PCPPs and Their Applications
Testing and Learning Convex Sets in the Ternary Hypercube
On the Computational Hardness Needed for Quantum Cryptography
Timeability of Extensive-Form Games
Local Decoding and Testing of Polynomials over Grids
Homophily and the Glass Ceiling Effect in Social Networks
Adaptive Boolean Monotonicity Testing in Total Influence Time
Sampling Arborescences in Parallel
Parity vs. AC0 with Simple Quantum Preprocessing
The Complexity of Linear Dependence Problems in Vector Spaces
Matrix Completion and Related Problems via Strong Duality
False Consensus, Information Theory, and Prediction Markets
Collective Tree Exploration via Potential Function Method
Tight Hardness Results for Training Depth-2 ReLU Networks
Bounded Indistinguishability for Simple Sources
Is Submodularity Testable?
Relaxing Common Belief for Social Networks
Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems
A Candidate for a Strong Separation of Information and Communication
Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023
Graph densification
Complete Problems for Multi-Pseudodeterministic Computations
Unitary Complexity and the Uhlmann Transformation Problem
Learning Time Dependent Choice
Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation
Symmetric LDPC Codes and Local Testing
On Parallel Repetition of PCPs
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups
Distribution free evolvability of polynomial functions over all convex loss functions
Gadgets and anti-gadgets leading to a complexity dichotomy
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
Rational arguments: single round delegation with sublinear verification
Graph Searching with Predictions
Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes
Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Rumors with Changing Credibility
Dimension Reduction for Clustering: The Curious Case of Discrete Centers
On the convergence of the Hegselmann-Krause system
Linear programming, width-1 CSPs, and robust satisfaction
Debordering Closure Results in Determinantal and Pfaffian Ideals
Testing Intersecting and Union-Closed Families
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio
Randomness and Fairness in Two-Sided Matching with Limited Interviews
Playing Games without Observing Payoffs
The Quantum Supremacy Tsirelson Inequality
Recovering Structured Probability Matrices
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields
Double Coverage with Machine-Learned Advice