yusuke1997/dblp-id-title huggingface dataset:
Fast, small-space algorithms for approximate histogram maintenance
Public-key Quantum money with a classical bank
Non-interactive delegation and batch NP verification from standard computational assumptions
Security-Preserving Hardness-Amplification for Any Regular One-Way Function
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
Multi-parameter Mechanisms for Consumer Surplus Maximization
Fast Computation of GCDs
On the Validity and Complexity of Bounded Resolution
Polynomial Algorithms for Multiple Processor Agreement
Non-Oblivious Hashing (Extended Abstract)
On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract)
Formal Languages and Power Series
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling
Decision tree complexity and Betti numbers
Concentration on the Boolean hypercube via pathwise stochastic analysis
Abstract Families of Deterministic Languages
Classical verification of quantum proofs
All Pairs Lightest Shortest Paths
Efficient quantum tomography
Polylogarithmic inapproximability
First to market is not everything: an analysis of preferential attachment with fitness
The Power of Negative Thinking in Multiplying Boolean Matrices
Balanced outcomes in social exchange networks
Excluded Grid Theorem: Improved and Simplified
The adaptive complexity of maximizing a submodular function
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty
On approximability of satisfiable k -CSPs: I
New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions
On gamma-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract)
On basing one-way functions on NP-hardness
Optimal Wiring between Rectangles
Sorting on a Mesh-Connected Parallel Computer
Decidability of the Multiplicity Equivalence of Multitape Finite Automata
Linear Unification
On paging with locality of reference
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point
General strong polarization
Nonlinear Dynamics for the Ising Model
Randomized versus Nondeterministic Communication Complexity
Efficient probabilistic checkable proofs and applications to approximation
A Characterization of Hoare's Logic for Programs with Pascal-like Procedures
Learning DNF in time 2 Õ(n 1/3 )
Approximations for the isoperimetric and spectral profile of graphs and related parameters
Low-distortion embeddings of general metrics into the line
Constant approximating k-clique is w[1]-hard
Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
Worst-case update times for fully-dynamic all-pairs shortest paths
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
Counting complexity classes for numeric computations II: algebraic and semialgebraic sets
Space-time Tradeoffs and First Order Problems in a Model of Programs
Majorizing Estimators and the Approximation of #P-Complete Problems
On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store
A Model of Computation for VLSI with Related Complexity Results
New algorithms and lower bounds for circuits with linear threshold gates
Sharp threshold results for computational complexity
Negation Can Be Exponentially Powerful
A new family of locally correctable codes based on degree-lifted algebraic geometry codes
Complexity Classes of Recursive Functions and the Existence of Complexity Gaps
Distributed computing theory: algorithms, impossibility results, models, and proofs
Sum of squares lower bounds for refuting any CSP
A Zero-One Law for Boolean Privacy (extended abstract)
Equations between Regular Terms and an Application to Process Logic
Narrow proofs may be spacious: separating space and width in resolution
Mechanism design with uncertain inputs: (to err is human, to forgive divine)
An analysis of one-dimensional schelling segregation
Dynamic algorithms for LIS and distance to monotonicity
Monotone monadic SNP and constraint satisfaction
Investigations of Fault-Tolerant Networks of Computers (Preliminary Version)
The Complexity of Perfect Zero-Knowledge (Extended Abstract)
Testing Distributional Assumptions of Learning Algorithms
Complexity theory for operators in analysis
On vertex sparsifiers with Steiner nodes
Learning in the Presence of Malicious Errors (Extended Abstract)
A unified framework for concurrent security: universal composability from stand-alone non-malleability
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA
Distributed exact shortest paths in sublinear time
Recursive composition and bootstrapping for SNARKS and proof-carrying data
Correcting Faults in Write-Once Memory
A o(n) monotonicity tester for boolean functions over the hypercube
Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
Sum-of-Squares Lower Bounds for Coloring Random Graphs
A Lower Bound for Randomized Algebraic Decision Trees
Small-Depth Counting Networks
The Computational Complexity of Algebraic Numbers
A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes
Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin
Quantum lower bounds by quantum arguments
Monotonicity testing over general poset domains
Transformations on Straight Line Programs-Preliminary Version
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Approximate near neighbors for general symmetric norms
Local Reorientation, Global Order, and Planar Topology (Preliminary Version)
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region
Relaxed Local Correctability from Local Testing
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011
A Framework for Building Data Structures from Communication Protocols
On the Pauli Spectrum of QAC0
From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement
An Efficient Network Synchronization Protocol
Parallel Computation Over Hyperbolic Groups
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Boosting simple learners
How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable
Localized Search in Sorted Lists
Randomized graph products, chromatic numbers, and Lovasz theta-function
Separating Tape Bounded Auxiliary Pushdown Automata Classes
The Meta-complexity of Secret Sharing
On the Optimal Evaluation of a Set of Bilinear Forms
Fast quantum byzantine agreement
Context-Free Grammars on Trees
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
QMA vs QCMA and Pseudorandomness
Simplex partitioning via exponential clocks and the multiway cut problem
The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract)
Universal points in the asymptotic spectrum of tensors
CSPs with global modular constraints: algorithms and hardness via polynomial representations
Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005
Provably secure session key distribution: the three party case
Interdomain routing and games
On targeting Markov segments
Local, Private, Efficient Protocols for Succinct Histograms
Exponential Separation of Quantum and Classical Communication Complexity
Stability of load balancing algorithms in dynamic adversarial systems
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
Budget feasible mechanism design: from prior-free to bayesian
Rethinking internet routing
Bipartite perfect matching is in quasi-NC
An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
Near-Optimal Derandomization of Medium-Width Branching Programs
On the Expressive Power of Dynamic Logic (Preliminary Report)
Near-optimal private approximation protocols via a black box transformation
Existence and Construction of Edge Disjoint Paths on Expander Graphs
Separations in query complexity based on pointer functions
Approximation algorithms for minimum-cost k-vertex connected subgraphs
Quantum Communication Advantage in TFNP
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Breaking the minsky-papert barrier for constant-depth circuits
One sketch for all: fast algorithms for compressed sensing
Stochastic Matching via In-n-Out Local Computation Algorithms
Word Problems Requiring Exponential Time: Preliminary Report
DNF sparsification beyond sunflowers
SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications
The power of multiple choices in online stochastic matching
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
Boosting in the presence of noise
The limits of pan privacy and shuffle privacy for learning and estimation
Affine projections of polynomials: extended abstract
On non-optimally expanding sets in Grassmann graphs
A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version)
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
The changing face of web search: algorithms, auctions and advertising
Practical post-quantum key agreement from generic lattices (invited talk)
Breaking quadratic time for small vertex connectivity and an approximation scheme
From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity
Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space
Optimal online buffer scheduling for block devices
Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Founding Cryptography on Oblivious Transfer
Numerical linear algebra in the streaming model
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities
An adaptive sublinear-time block sparse fourier transform
Multidimensional approximate agreement in Byzantine asynchronous systems
Rational proofs
Forests, Frames and Games: Algorithms for Matroid Sums and Applications
A Constant-Factor Approximation Algorithm for the k -Median Problem (Extended Abstract)
Storage Representations for Tree-Like Data Structures
Finding even cycles faster via capped k-walks
Sparsifying Generalized Linear Models
Succinct sampling from discrete distributions
A General Completeness Theorem for Two-Party Games
Faster all-pairs shortest paths via circuit complexity
Almost Linear Size Edit Distance Sketch
Ramanujan coverings of graphs
Duality Applied to the Complexity of Matrix Multiplications and other Bilinear Forms
On the efficiency of local decoding procedures for error-correcting codes
Deterministic construction of a high dimensional l p section in l 1 n for any p <2
Recognizing Primes in Random Polynomial Time
Solving the Correlation Cluster LP in Sublinear Time
Distributed weighted min-cut in nearly-optimal time
On algorithms for discrete and approximate brouwer fixed points
Unique Normal Forms in Term Rewriting Systems with Repeated Variables
Why extension-based proofs fail
Aligning sequences via an evolutionary tree: complexity and approximation
Sublinear Algorithms for (1.5+ε)-Approximate Matching
Random knapsack in expected polynomial time
Constant-factor approximation of near-linear edit distance in near-linear time
On the Complexity of Random Satisfiability Problems with Planted Solutions
On dual minimum cost flow algorithms (extended abstract)
One Help Bit Doesn't Help
Fast moment estimation in data streams in optimal space
Approximation algorithms for geometric shortest path problems
Rapid Identification of Repeated Patterns in Strings, Trees and Arrays
Efficient density estimation via piecewise polynomial approximation
Polylogarithmic-time deterministic network decomposition and distributed derandomization
On the Computational Power of QAC0 with Barely Superlinear Ancillae
An Unusual Application of Program-Proving
Explicit, almost optimal, epsilon-balanced codes
Improved communication complexity of fault-tolerant consensus
Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
Static and Dynamic Evaluation of QoS Properties
Approaching the Quantum Singleton Bound with Approximate Error Correction
Intercalation Theorems for Stack Languages
Maintaining Order in a Linked List
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Faster integer multiplication
Black-box non-black-box zero knowledge
Learning mixtures of linear regressions in subexponential time via Fourier moments
Building triangulations using epsilon-nets
Towards a Theory of Software Protection and Simulation by Oblivious RAMs
Making Games Short (Extended Abstract)
Biased Random Walks
An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography
Decoding multivariate multiplicity codes on product sets
Two Tapes are Better than One for Nondeterministic Machines
Finding a maximum weight triangle in n 3-Delta time, with applications
Average-case hardness of NP from exponential worst-case hardness assumptions
Feasibility Testing for Systems of Real Quadratic Equations
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version)
Generalized matrix completion and algebraic natural proofs
One-dimensional quantum walks
Random Graph Matching at Otter's Threshold via Counting Chandeliers
The Design of Parsers for Incremental Language Processors
On Minimal-Program Complexity Measures
Nearly complete graphs decomposable into large induced matchings and their applications
Fast fencing
On Computing the Minima of Quadratic Forms (Preliminary Report)
Channel Routing in VLSI (Extended Abstract)
Deciding first-order properties of nowhere dense graphs
Degrees of Translatability and Canonical Forms in Program Schemas: Part I
On the hardness of the noncommutative determinant
Nearly optimal static Las Vegas succinct dictionary
Simple PCPs with poly-log rate and query complexity
A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field
An Efficient Quantum Parallel Repetition Theorem and Applications
Hardness of cut problems in directed graphs
Online edge coloring via tree recurrences and correlation decay
Bounding the menu-size of approximately optimal auctions via optimal-transport duality
A lower bound for integer multiplication with read-once branching programs
Influences in Mixing Measures
Generalized Selection and Ranking (Preliminary Version)
Fully Dynamic Planarity Testing (Extended Abstract)
On the Possibility and Impossibility of Achieving Clock Synchronization
Approximately stable committee selection
Market equilibrium via the excess demand function
The parallel repetition of non-signaling games: counterexamples and dichotomy
High-rate codes with sublinear-time decoding
Spatial gossip and resource location protocols
One-Way Functions Are Essential for Single-Server Private Information Retrieval
On the Communication Complexity of Approximate Pattern Matching
An homotopy method for l p regression provably beyond self-concordance and in input-sparsity time
A Duality between One-Way Functions and Average-Case Symmetry of Information
Depth through breadth, or why should we attend talks in other areas?
The 4/3 additive spanner exponent is tight
Approximations of General Independent Distributions
Inapproximability of pure nash equilibria
A randomized polynomial-time simplex algorithm for linear programming
Probabilistic rank and matrix rigidity
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing
Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders
Black-box constructions for secure computation
Improved Algorithms for Integer Programming and Related Lattice Problems
AG Codes Achieve List Decoding Capacity over Constant-Sized Fields
Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound
Linear Representation of Tree Structure: A Mathematical Theory of Parenthesis-Free Notations
Coboundary Expansion of Coset Complexes
Checking Computations in Polylogarithmic Time
Finite Monoids and the Fine Structure of NC¹
On the Angular Resolution of Planar Graphs
Space lower bounds for distance approximation in the data stream model
Parallel Evaluation of Division-Free Arithmetic Expressions
Tight(er) worst-case bounds on dynamic searching and priority queues
Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time
Non-malleable extractors and symmetric key cryptography from weak secrets
On the performance of greedy algorithms in packet buffering
Molecular Scale Heat Engines and Scalable Quantum Computation
Improved bounds for perfect sampling of k-colorings in graphs
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
Explicit N-vertex graphs with maximum degree K and diameter [1+o(1)] log K-1 N for each K-1 a prime power
Efficient stopping rules for Markov chains
The Decidability of the Reachability Problem for Vector Addition Systems (Preliminary Version)
Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
A random graph model for massive graphs
On the Power of Randomization in Online Algorithms (Extended Abstract)
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Descriptive complexity theory over the real numbers
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019
Lower Bounds on Communication Complexity
Approximating the domatic number
Efficient LR(1) Processor Construction
Cryptographic Protocols
Tree-Manipulating Systems and Church-Rosser Theorems
Searching for Primitive Roots in Finite Fields
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Computing Betti Numbers via Combinatorial Laplacians
Tight security proofs for the bounded-storage model
Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version)
Tractable Agreement Protocols
Improved data structures for fully dynamic biconnectivity
An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Properties that Characterize LOGCFL
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014
Space efficient dynamic stabbing with fast queries
Computing the median with uncertainty
Static data structure lower bounds imply rigidity
Isotopic implicit surface meshing
Multidimensional Quantum Walks
Operational and Semantic Equivalence between Recursive Programs
Optimal hierarchical decompositions for congestion minimization in networks
Data Structures for On-Line Updating of Matroid Intersection Solutions (Preliminary Version)
Optimal Bounds for the Predecessor Problem
Local Geometry of NAE-SAT Solutions in the Condensation Regime
Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract)
Dynamic Deflection Routing on Arrays (Preliminary Version)
The Complexity of Priority Queue Maintenance
Trading Space for Time in Undirected s-t Connectivity
Constant Degree Networks for Almost-Everywhere Reliable Transmission
A randomized fully polynomial time approximation scheme for the all terminal network reliability problem
Breaking the n k barrier for minimum k -cut on simple graphs
Locally testable codes with constant rate, distance, and locality
Hypercontractivity on HDX II: Symmetrization and q-Norms
Approximation resistance on satisfiable instances for predicates with few accepting inputs
The metric relaxation for 0 -extension admits an Ω(log 2/3 k) gap
Minimum bisection is fixed parameter tractable
Weighted min-cut: sequential, cut-query, and streaming algorithms
Efficient Fault Tolerant Routings in Networks
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance
Complexity of Graph Partition Problems
Single-Source Shortest Paths with Negative Real Weights in Õ(mn 8/9 ) Time
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces
Persistent lists with catenation via recursive slow-down
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
Hypercontractivity on high dimensional expanders
A 3-Space Partition and Its Applications (Extended Abstract)
Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract)
Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane
The Complexity of the Simplex Method
Limits on the Provable Consequences of One-Way Permutations
Multiway cut, pairwise realizable distributions, and descending thresholds
Interactive compression to external information
Testing conditional independence of discrete distributions
On Determining the Genus of a Graph in O(v^O(g)) Steps
Monotone Contractions
A node-capacitated okamura-seymour theorem
Multiple intents re-ranking
Random (log n)-CNF Are Hard for Cutting Planes (Again)
An Interruptible Algorithm for Perfect Sampling via Markov Chains
Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
The Cost of the Missing Bit: Communication Complexity with Help
Alternation and the Power of Nondeterminism
Interactive proofs of proximity: delegating computation in sublinear time
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract)
Complexity-Theoretic Implications of Multicalibration
Testing symmetric properties of distributions
Strongly exponential lower bounds for monotone computation
Hardness of approximate nearest neighbor search
Towards Optimal Simulations of Formulas by Bounded-Width Programs
Resettable zero-knowledge (extended abstract)
List-decodable covariance estimation
Rational secret sharing and multiparty computation: extended abstract
Non-malleable codes from additive combinatorics
CREW PRAMs and Decision Trees
Parallelism in Random Access Machines
Non-interactive and reusable non-malleable commitment schemes
BLASTING through the Information Theoretic Barrier with FUSION TREES
Computational complexity and knowledge complexity (extended abstract)
Incremental cryptography and application to virus protection
The Cryptographic Security of Truncated Linearly Related Variables
DNF Learning via Locally Mixing Random Walks
A constant-factor approximation algorithm for the asymmetric traveling salesman problem
Computational Parallels between the Regular and Context-Free Languages
Tensor-based hardness of the shortest vector problem to within almost polynomial factors
Characterization of Flowchartable Recursions (Short Version)
Zero-knowledge from secure multiparty computation
Embedding Tree Metrics Into Low Dimensional Euclidean Spaces
Area-convexity, l ∞ regularization, and undirected multicommodity flow
The impossibility of efficient quantum weak coin flipping
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
A guessing game and randomized online algorithms
Subgraph sparsification and nearly optimal ultrasparsifiers