yusuke1997/dblp-id-title huggingface dataset:
A Qubit, a Coin, and an Advice String Walk into a Relational Problem
Computation-Aware Data Aggregation
Explicit SoS Lower Bounds from High-Dimensional Expanders
Error Correction for Message Streams
Compression without a common prior: an information-theoretic justification for ambiguity in language
Sample Efficient Identity Testing and Independence Testing of Quantum States
A Variant of the VC-Dimension with Applications to Depth-3 Circuits
Is It Easier to Count Communities Than Find Them?
Lower Bounds: From Circuits to QBF Proof Systems
Fine-Grained Equivalence for Problems Related to Integer Linear Programming
A Unifying Framework for Characterizing and Computing Width Measures
Counting Subgraphs in Somewhere Dense Graphs
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D
Budget-Smoothed Analysis for Submodular Maximization
Matching Is as Easy as the Decision Problem, in the NC Model
High-Dimensional Expanders from Expanders
Decision trees, protocols and the entropy-influence conjecture
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems
Unexpected Power of Random Strings
Optimal Communication Complexity of Chained Index
On the Power of Computationally Sound Interactive Proofs of Proximity
Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity
Very Simple and Efficient Byzantine Agreement
Robust optimization in the presence of uncertainty
Property Testing with Online Adversaries
Sunflowers and Testing Triangle-Freeness of Functions
Further Limitations of the Known Approaches for Matrix Multiplication
On the power of many one-bit provers
Extractors for Polynomial Sources over 𝔽 2
A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit
Marginal hitting sets imply super-polynomial lower bounds for permanent
Algorithms, Bounds, and Strategies for Entangled XOR Games
Distributed Computing with Adaptive Heuristics
Fast Local Computation Algorithms
Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions
Errorless Versus Error-Prone Average-Case Complexity
Can Almost Everybody be Almost Happy?
On Low-End Obfuscation and Learning
Garland's Technique for Posets and High Dimensional Grassmannian Expanders
An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes
Lower Bounds Beyond DNF of Parities
On persistent homotopy, knotted complexes and the Alexander module
Cache Replacement Policies for Multicore Processors
Lower Bounds for Symmetric Circuits for the Determinant
Cube vs. Cube Low Degree Test
On Solving Linear Systems in Sublinear Time
Local Access to Random Walks
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
Ordered Graph Limits and Their Applications
One-Way Functions vs. TFNP: Simpler and Improved
Cryptography for Parallel RAM from Indistinguishability Obfuscation
Coordination mechanisms from (almost) all scheduling policies
Delaunay Triangulations with Predictions
High dimensional expanders and property testing
Two Bases Suffice for QMA ₁-Completeness
Lower Bounds on FSS from Dynamic Data Structures
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Decoding Balanced Linear Codes with Preprocessing
Smoothed Analysis of Dynamic Graph Algorithms
Edge Estimation with Independent Set Oracles
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
General Computation Using Slidable Tiles with Deterministic Global Forces
Proofs of Proximity for Distribution Testing
On Polynomially Many Queries to NP or QMA Oracles
New Query Lower Bounds for Submodular Function Minimization
Indistinguishability Obfuscation of Null Quantum Circuits and Applications
Compressed matrix multiplication
Toward the Impossibility of Perfect Complete Quantum PKE from OWFs
Kolmogorov Complexity Characterizes Statistical Zero Knowledge
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations
Can theories be tested?: a cryptographic treatment of forecast testing
Game Theory with Costly Computation: Formulation and Application to Protocol Security
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
Finding Almost-Perfect Graph Bisections
Rethinking Fairness for Human-AI Collaboration (Extended Abstract)
Building one-time memories from isolated qubits: (extended abstract)
Interactive Proofs for Synthesizing Quantum States and Unitaries
Karchmer-Wigderson Games for Hazard-Free Computation
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Verifiably Truthful Mechanisms
Distributed Vertex Cover Reconfiguration
Pseudorandom Strings from Pseudorandom Quantum States
Very Sparse Additive Spanners and Emulators
Homomorphic Indistinguishability Obfuscation and Its Applications
Direct sum fails for zero error average communication
Parameterization Above a Multiplicative Guarantee
A New Approach to Strongly Polynomial Linear Programming
Mechanism design in large games: incentives and privacy
Random Restrictions of Bounded Low Degree Polynomials Are Juntas
Approximating Cumulative Pebbling Cost Is Unique Games Hard
Time and Space Efficient Deterministic List Decoding
Are Stable Instances Easy?
Stabbing Planes
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
Quantum Query Algorithms are Completely Bounded Forms
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions
Cryptographic Complexity Classes and Computational Intractability Assumptions
Provability of the Circuit Size Hierarchy and Its Consequences
Query Complexity Lower Bounds for Reconstruction of Codes
From randomizing polynomials to parallel algorithms
Tree codes and a conjecture on exponential sums
Fairness in the k-Server Problem
Algorithms on evolving graphs
Tiered Random Matching Markets: Rank Is Proportional to Popularity
Spectral sparsification via random spanners
Training (Overparametrized) Neural Networks in Near-Linear Time
Deterministic Rateless Codes for BSC
The Secretary Problem with Predictions and a Chosen Order
Symmetric Algebraic Circuits and Homomorphism Polynomials
Approximate Unitary k-Designs from Shallow, Low-Communication Circuits (Extended Abstract)
What Circuit Classes Can Be Learned with Non-Trivial Savings?
On the Black-Box Complexity of Correlation Intractability
On the Communication Complexity of Key-Agreement Protocols
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
Shrinkage of Decision Lists and DNF Formulas
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games
The Random-Query Model and the Memory-Bounded Coupon Collector
Efficient Semantic Communication via Compatible Beliefs
On the Complexity of Symmetric Polynomials
Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing
L p Testing and Learning of Discrete Distributions
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Graph Reconstruction via MIS Queries
Differential Privacy on Trust Graphs
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
Larger Corner-Free Sets from Combinatorial Degenerations
Matrix Multiplication via Matrix Groups
Deterministic 3SUM-Hardness
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Multiscale Entropic Regularization for MTS on General Metric Spaces
Robust Resource Allocation via Competitive Subsidies
Black-box obfuscation for d-CNFs
The Entropy of Lies: Playing Twenty Questions with a Liar
Combinatorial Lower Bounds for 3-Query LDCs
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication
Computing Equilibrium Points of Electrostatic Potentials
Parametric digital auctions
Continuous Tasks and the Asynchronous Computability Theorem
A Tight Lower Bound For Non-Coherent Index Erasure
Mechanism Design with Moral Bidders
Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method
Noisy Boolean Hidden Matching with Applications
Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract)
Testing Properties of Multiple Distributions with Few Samples
Private interactive communication across an adversarial channel
Diversity in Evolutionary Dynamics (Extended Abstract)
Doubly Sub-Linear Interactive Proofs of Proximity
Delegated Stochastic Probing
Privacy-Preserving Public Information for Sequential Games
Fault Tolerant Subgraphs with Applications in Kernelization
11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, Washington, USA, January 12-14, 2020
Mechanism Design with Strategic Mediators
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions (Extended Abstract)
On Approximating the Entropy of Polynomial Mappings
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Erasure-Resilient Sublinear-Time Graph Algorithms
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality
Online Computation with Untrusted Advice
Quantitative Correlation Inequalities via Semigroup Interpolation
A Complexity View of Markets with Social Influence
Bitcoin: A Natural Oligopoly
Quantum Codes from High-Dimensional Manifolds
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016
Metatheorems for Dynamic Weighted Matching
Backdoor Defense, Learnability and Obfuscation
FPT Approximations for Connected Maximum Coverage
Preference-Informed Fairness
Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP
Sample Complexity Bounds for Influence Maximization
An Axiomatic Approach to Community Detection
Analytical Tools for Natural Algorithms
The truth behind the myth of the folk theorem
Finite Matrix Multiplication Algorithms from Infinite Groups
Hardness Amplification of Optimization Problems
What Does Dynamic Optimality Mean in External Memory?
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs
Algorithmic Aspects of Private Bayesian Persuasion
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
Optimal Sub-Gaussian Mean Estimation in Very High Dimensions
On beating the hybrid argument
Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis
The Chromatic Number of Kneser Hypergraphs via Consensus Division
High-confidence predictions under adversarial uncertainty
Small Sunflowers and the Structure of Slice Rank Decompositions
9th Innovations in Theoretical Computer Science Conference, ITCS 2018, Cambridge, MA, USA, January 11-14, 2018
Algorithmic Collusion Without Threats
Symmetric Formulas for Products of Permutations
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
A Quantum Unique Games Conjecture
Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance
The Space "Just Above" BQP
Auditability and the Landscape of Distance to Multicalibration
Nash Social Welfare, Matrix Permanent, and Stable Polynomials
On the power of nonuniformity in proofs of security
Approximately Strategyproof Tournament Rules in the Probabilistic Setting
On the Existence of Competitive Equilibrium with Chores
Time- and Communication-Efficient Overlay Network Construction via Gossip
Cursed yet Satisfied Agents
Lower Bounds on Tree Covers
Efficient Catalytic Graph Algorithms
Differentially private data analysis of social networks via restricted sensitivity
From Local to Robust Testing via Agreement Testing
Economical Graph Discovery
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
Distributional Property Testing in a Quantum World
Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE
On the Power of Learning from k-Wise Queries
The Need for Structure in Quantum Speedups
Uniformity Testing Under User-Level Local Privacy
Limitations of Membership Queries in Testable Learning
Decompositions of triangle-dense graphs
Exponential-Time Approximation Schemes via Compression
Exact Completeness of LP Hierarchies for Linear Codes
On the Complexity of #CSP^d
Fraud Detection for Random Walks
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
Extremely Deep Proofs
Smooth Nash Equilibria: Algorithms and Complexity
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing
New Bounds for Circular Trace Reconstruction
Perfect Simulation of Las Vegas Algorithms via Local Computation
Optimal Bounds for Dominating Set in Graph Streams
Time hierarchies for sampling distributions
Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
Quantum Event Learning and Gentle Random Measurements
On Learning Mixture Models for Permutations
Voting with Coarse Beliefs
Fast Cross-Polytope Locality-Sensitive Hashing
Smoothed Efficient Algorithms and Reductions for Network Coordination Games
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings
Is There an Oblivious RAM Lower Bound?
Simulating Random Walks on Graphs in the Streaming Model
Total Search Problems in ZPP
Cryptography from Information Loss
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity
The Message Complexity of Distributed Graph Optimization
On Oracles and Algorithmic Methods for Proving Lower Bounds
Hamiltonian Sparsification and Gap-Simulation
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data
On Hardness of Approximating the Parameterized Clique Problem
3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time
Embeddings and Labeling Schemes for A
Rank Lower Bounds on Non-Local Quantum Computation
Approximately optimal mechanism design via differential privacy
The Importance of the Spectral Gap in Estimating Ground-State Energies
Foundations of Homomorphic Secret Sharing
Sequential decision making with vector outcomes
A New Analysis of Differential Privacy's Generalization Guarantees
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
On the Communication Complexity of High-Dimensional Permutations
A High Dimensional Cramer's Rule Connecting Homogeneous Multilinear Equations to Hyperdeterminants
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?
Probing to Minimize
Sampling List Packings
On Fairness and Stability in Two-Sided Matchings
Sharp Threshold Rates for Random Codes
Intersection Classes in TFNP and Proof Complexity
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds
The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions
Long Term Memory and the Densest K-Subgraph Problem
Complexity of approximating CSP with balance / hard constraints
Bounds on the QAC^0 Complexity of Approximating Parity
Relax, No Need to Round: Integrality of Clustering Formulations
Agnostic Learning with Unknown Utilities
Color Fault-Tolerant Spanners
On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions
Concentration of Submodular Functions and Read-k Families Under Negative Dependence
Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples
When to Give up on a Parallel Implementation
Circuit Lower Bounds, Help Functions, and the Remote Point Problem
List decoding subspace codes from insertions and deletions
On White-Box Learning and Public-Key Encryption
Convergence Results for Neural Networks via Electrodynamics
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers
Beyond the Nash Equilibrium Barrier
Separating Two-Round Secure Computation From Oblivious Transfer
Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks
Reaching Consensus on Social Networks
Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs
AC⁰[p]-Frege Cannot Efficiently Prove That Constant-Depth Algebraic Circuit Lower Bounds Are Hard
Robust Quantum Entanglement at (Nearly) Room Temperature
A Note on the Quantum Query Complexity of Permutation Symmetric Functions
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
Confusion Matrix Design for Downstream Decision-Making (Extended Abstract)
A Parameterized-Complexity Framework for Finding Local Optima
Weight Distribution and List-Decoding Size of Reed-Muller Codes
The Paulsen Problem Made Simple
10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, January 10-12, 2019
Two Combinatorial MA-Complete Problems
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round
Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Symmetric Quantum Computation
Improper Learning by Refuting
Kernelization of Counting Problems
Cloning Games, Black Holes and Cryptography
Mechanisms With Costly Knowledge
Influence Maximization in Ising Models
Learning Reserve Prices in Second-Price Auctions
Fairness through awareness
Barriers in cryptography with weak, correlated and leaky sources
Proving Unsatisfiability with Hitting Formulas
Semi-Random Graphs, Robust Asymmetry, and Reconstruction
On the possibilities and limitations of pseudodeterministic algorithms
Information Value of Two-Prover Games
Eliminating Intermediate Measurements Using Pseudorandom Generators
Total Functions in the Polynomial Hierarchy
Strategic Payments in Financial Networks
Local Computation Algorithms for Spanners
Quantum Merlin-Arthur and Proofs Without Relative Phase
Targeted malleability: homomorphic encryption for restricted computations
Interactive Coding with Constant Round and Communication Blowup
The Strength of Equality Oracles in Communication
Learning Discrete Distributions from Untrusted Batches
On Price versus Quality
On Computing Homological Hitting Sets
Overlapping Qubits
Quantum Communication Complexity of Classical Auctions
On Distributed Differential Privacy and Counting Distinct Elements
Integer feasibility of random polytopes: random integer programs
Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic
Revenue Maximization via Nash Implementation
Prior-Independent and Subgame Optimal Online Algorithms
Distributed Quantum Proofs for Replicated Data
Simultaneous Private Learning of Multiple Concepts
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm
Non-Interactive Proofs of Proximity
Redrawing the boundaries on purchasing data from privacy-sensitive individuals
Round-Vs-Resilience Tradeoffs for Binary Feedback Channels
An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets
A Local-Search Algorithm for Steiner Forest
Why are Images Smooth?
High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)
Pseudorandom Generators for Low Sensitivity Functions
Diffie-Hellman Key Exchange from Commutativity to Group Laws
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
The Journey from NP to TFNP Hardness
Clustering Permutations: New Techniques with Streaming Applications
A Gaussian Fixed Point Random Walk
Black-Box Constructive Proofs Are Unavoidable
Properties and applications of boolean function composition
Simple Norm Bounds for Polynomial Random Matrices via Decoupling
Fairness Under Composition
Quantum Distributed Algorithms for Detection of Cliques
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
Adventures in Monotone Complexity and TFNP
HappyMap : A Generalized Multicalibration Method
The Duality Gap for Two-Team Zero-Sum Games
Small-Box Cryptography
Tensor Reconstruction Beyond Constant Rank
Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope
List Decoding Reed-Solomon Codes in the Lee, Euclidean, and Other Metrics
Pseudo-Deterministic Streaming
From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology
Vertex Fault-Tolerant Emulators
Lower Bounds on Stabilizer Rank
Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model
Semantic Security under Related-Key Attacks and Applications
Fully Quantum Computational Entropies (Extended Abstract)
Pre-Constrained Encryption
Lower Bounds and Separations for Torus Polynomials
Extracting Dual Solutions via Primal Optimizers
H-wise independence
Combinatorial Approximation Algorithms for MaxCut using Random Walks
List Decoding Bounds for Binary Codes with Noiseless Feedback
Lower Bounds for Planar Arithmetic Circuits
Quantum Pseudoentanglement
Mixing in Non-Quasirandom Groups
A General Framework for Low Soundness Homomorphism Testing
Hardness of Dynamic Tree Edit Distance and Friends
Abstract Cryptography
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers
Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)
Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement
Robust Streaming Against Low-Memory Adversaries
How to Use Nondeterminism in Cryptography
Catch them if you can: how to serve impatient users
Locality-Preserving Hashing for Shifts with Connections to Cryptography
Counterexamples to the Low-Degree Conjecture
Rigidity in Mechanism Design and Its Applications
Randomness Extraction from Somewhat Dependent Sources
Interaction-Preserving Compilers for Secure Computation
Individual Fairness in Advertising Auctions Through Inverse Proportionality
Improved Lower Bounds for 3-Query Matching Vector Codes
Partial tests, universal tests and decomposability
Reduction from Non-Unique Games to Boolean Unique Games
Differentially Private Medians and Interior Points for Non-Pathological Data
The Complexity of Problems in P Given Correlated Instances
Pseudo-Deterministic Proofs
Rate-independent computation in continuous chemical reaction networks
Time-Traveling Simulators Using Blockchains and Their Applications
A PAC Approach to Application-Specific Algorithm Selection
Testing Properties of Collections of Distributions
The Complexity of Finding Fair Independent Sets in Cycles
Proofs of Catalytic Space
On the Computational Complexity of Limit Cycles in Dynamical Systems
Modularity and Graph Expansion
Quantum Proofs of Deletion for Learning with Errors
SOS Is Not Obviously Automatizable, Even Approximately
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
Local Transformations of Bipartite Entanglement Are Rigid