yusuke1997/dblp-id-title huggingface dataset:
On (Un)predictability of Formal Languages (Extended Abstract)
Complexity theoretic limitations on learning halfspaces
Near-optimal distortion bounds for embedding doubling spaces into L 1
The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (Extended Abstract)
Probabilistically Checkable Proofs with Zero Knowledge
Finding Minimum-Cost Circulations by Canceling Negative Cycles
Short length versions of Menger's theorem (Extended Abstract)
The Complexity of Finding Periods
A PSPACE construction of a hitting set for the closure of small algebraic circuits
The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring
Optimal sequence length requirements for phylogenetic tree reconstruction with indels
Approximately counting integral flows and cell-bounded contingency tables
Limits of provable security from standard assumptions
On communication over an entanglement-assisted quantum channel
On the effect of randomness on planted 3-coloring models
Capacity approaching coding for low noise interactive quantum communication
Weak Alternating Automata and Tree Automata Emptiness
A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation
Fast Allocation of Nearby Resources in a Distributed System
Adjacency Labeling Schemes and Induced-Universal Graphs
Answering n {2+o(1)} counting queries with differential privacy is hard
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract)
Tight bounds for single-pass streaming complexity of the set cover problem
Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints
Testing monotone high-dimensional distributions
On the Degree of Boolean Functions as Real Polynomials
Proof of a Conjecture of R. Kannan
Online local learning via semidefinite programming
Algorithmic Aspects of Vertex Elimination
On the impossibility of approximate obfuscation and applications to resettable cryptography
Constant-Time Parallel Integer Sorting (Extended Abstract)
Expanders Obtained from Affine Transformations (Preliminary Version)
Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract)
Tight Results for Online Convex Paging
Counting Random k-SAT near the Satisfiability Threshold
The query complexity of certification
The approximate degree of DNF and CNF formulas
Natural proofs
Quasi-polynomial hitting-set for set-depth-Δ formulas
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
On Syntax-Directed Transduction and Tree Transducers
Graph expansion and the unique games conjecture
Parallel Sampling via Counting
How long does it take to catch a wild kangaroo?
Clifford algebras and approximating the permanent
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube
Explicit lower bound of 4.5n - o(n) for boolena circuits
Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators
Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations
The Strong Exponential Hierarchy Collapses
Stateless distributed gradient descent for positive linear programs
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
An Efficient Algorithm for Computing Optimal Desk Merge Patterns (Extended Abstract)
Sublinear algorithms for testing monotone and unimodal distributions
Lower bounds for randomized mutual exclusion
Computing Permutations with Double-Ended Queues, Parallel Stacks and Parallel Queues
Robust linear regression: optimal rates in polynomial time
Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
On randomized online scheduling
Locally Sampleable Uniform Symmetric Distributions
Learning Sat- k -DNF Formulas from Membership Queries
Approximation algorithms for hierarchical location problems
Faster shortest-path algorithms for planar graphs
Universally-optimal distributed algorithms for known topologies
Asymmetric k-center is log * n -hard to approximate
Explicit capacity-achieving list-decodable codes
Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk)
Optimal mean-based algorithms for trace reconstruction
Graph partitioning using single commodity flows
Jump PDA's, Deterministic Context-Free Languages Principal AFDLs and Polynomial Time Recognition-Extended Abstract
Computing quartet distance is equivalent to counting 4-cycles
On agnostic boosting and parity learning
On the Complexity of RAM with Various Operation Sets
The Shortest Vector Problem in L 2 is NP -hard for Randomized Reductions (Extended Abstract)
Exponential separations in the energy complexity of leader election
On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM
Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
From average case complexity to improper learning complexity
Approximation algorithms for bipartite matching with metric and geometric costs
Exponential separations for one-way quantum communication complexity, with applications to cryptography
Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
The pattern matrix method for lower bounds on quantum communication
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications
Distributed verification and hardness of distributed approximation
A converse to Banach's fixed point theorem and its CLS-completeness
Equational Theories and Database Constraints
Spectral analysis of data
The communication complexity of payment computation
A Linear-Time Algorithm for a Special Case of Disjoint Set Union
Cryptographic Characterization of Quantum Advantage
Circuits and Local Computation
Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm
Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract
The Closure of Monadic NP (Extended Abstract)
The topology of wireless communication
Tight rmr lower bounds for mutual exclusion and other problems
The Randomized k-Server Conjecture Is False!
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Gowers uniformity, influence of variables, and PCPs
Two-Dimensional Alternating Turing Machines
An improved approximation algorithm for TSP in the half integral case
Inaccessible entropy
Speed-Ups by Changing the Order in Which Sets are Enumerated (Preliminary Version)
An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals
Optimization with Pattern-Avoiding Input
Dichotomization, Reachability, and the Forbidden Subgraph Problem (Extended Abstract)
A framework for dynamic matching in weighted graphs
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Polynomial Time Solutions of Some Problems in Computational Algebra
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Omnipredicting Single-Index Models with Multi-index Models
Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract)
Distributed exact weighted all-pairs shortest paths in near-linear time
Black-box concurrent zero-knowledge requires Omega~(log n) rounds
Almost random graphs with simple hash functions
Better Coloring of 3-Colorable Graphs
On Some Deterministic Space Complexity Problems
Monotone Circuits for Connectivity Require Super-logarithmic Depth
Extractors for sum of two sources
A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract)
On the Complexity of Radio Communication (Extended Abstract)
Realistic Analysis of Some Randomized Algorithms
Optimal probabilistic fingerprint codes
Normal subgroup reconstruction and quantum computation using group representations
A PRG for lipschitz functions of polynomials with applications to sparsest cut
A functional equation often arising in the analysis of algorithms (extended abstract)
Parallelizing greedy for submodular set function maximization in matroids and beyond
The Analysis of Closed Hashing under Limited Randomness (Extended Abstract)
Representing hard lattices with O(n log n) bits
Primal beats dual on online packing LPs in the random-order model
Strict polynomial-time in simulation and extraction
Learning poisson binomial distributions
Quasi-Realtime Languages-Extended Abstract
Efficient quantum tomography II
Derandomization of auctions
New hardness results for congestion minimization and machine scheduling
Path Systems and Language Recognition
Distributed (∆+1)-coloring in sublogarithmic rounds
A Linear-Time Algorithm for Triangulating Simple Polygons
Tight cell probe bounds for succinct Boolean matrix-vector multiplication
On The Relationship between Finite Automata, Finite Monoids, and Prefix Codes
XOR lemmas for resilient functions against polynomials
Provably near-optimal sampling-based algorithms for Stochastic inventory control models
Towards the Erdős-Gallai Cycle Decomposition Conjecture
List decoding algorithms for certain concatenated codes
Fully Dynamic k-Median with Near-Optimal Update Time and Recourse
Constant inapproximability for PPA
Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy
Matchings in lattice graphs
On randomized one-round communication complexity
Quantum Computation of Fourier Transforms over Symmetric Groups
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (Extended Abstract)
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
On Time-Space Classes and Their Relation to the Theory of Real Addition
Byzantine agreement in polynomial expected time: [extended abstract]
Set similarity search beyond MinHash
Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version)
Virtual Memory Algorithms (Preliminary Version)
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006
Every locally characterized affine-invariant property is testable
Hadwiger's conjecture is decidable
Distributed (delta+1)-coloring in linear (in delta) time
Black-Box PPP Is Not Turing-Closed
Polynomial pass lower bounds for graph streaming algorithms
A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report)
Approximating Binary Longest Common Subsequence in Almost-Linear Time
Exponential improvement in precision for simulating sparse Hamiltonians
On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract)
An Interactive Information Odometer and Applications
Graph Ramsey Theory and the Polynomial Hierarchy
The Inherent Ambiguity Partial Algorithm Problem for Context Free Languages
Shape of diffusion and size of monochromatic region of a two-dimensional spin system
Choosing a learning team: a topological approach
Formal Models for Some Features of Programming Languages
Computing in Quotient Groups
The biased coin problem
Tight approximation ratio of anonymous pricing
Are Lower Bounds Easier over the Reals?
A read-once branching program lower bound of Omega(2 n/4 ) for integer multiplication using universal
Private approximation of NP-hard functions
Relating two property testing models for bounded degree directed graphs
Computing Local Dimension of a Semialgebraic Set
The Process Complexity and Effective Random Tests
Simulation beats richness: new data-structure lower bounds
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
New Layouts for the Shuffle-Exchange Graph (Extended Abstract)
A quantum algorithm for computing the unit group of an arbitrary degree number field
Read-once polynomial identity testing
Over Words, Two Variables Are as Powerful as One Quantifier Alternation
Nonlocal games, compression theorems, and the arithmetical hierarchy
Topologically Sweeping an Arrangement
On the Extremely Fair Treatment of Probabilistic Algorithms
Distributed Shortest Paths Algorithms (Extended Abstract)
Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers
Random sampling in cut, flow, and network design problems
The Decision Problem for the Probabilities of Higher-Order Properties
Pricing combinatorial markets for tournaments
On the Random Oracle Hypothesis
Contextual search in the presence of irrational agents
How to use indistinguishability obfuscation: deniable encryption, and more
Classes of Semigroups and Classes of Sets
Doubly Lexical Orderings of Matrices
Distributed Algorithms for Synchronizing Interprocess Communication within Real Time
Complexity Measures for Regular Expressions
Complex tilings
A Result on the Relationship between Simple Precedence Languages and Reducing Transition Languages
Robust testing of low dimensional functions
Robust lower bounds for communication and stream computation
Log-rank and lifting for AND-functions
Subquadratic-time factoring of polynomials over finite fields
Hop-constrained oblivious routing
Positive semidefinite programming: mixed, parallel, and width-independent
On Line Context Free Language Recognition in Less than Cubic Time (Extended Abstract)
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
A simpler algorithm and shorter proof for the graph minor decomposition
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
On Finding Lowest Common Ancestors in Trees
History-Independent Concurrent Hash Tables
Testing of matrix properties
How well do local algorithms solve semidefinite programs?
Linear bandits with limited adaptivity and learning distributional optimal design
Community detection thresholds and the weak Ramanujan property
Self-testing of universal and fault-tolerant sets of quantum gates
Proportional response dynamics leads to market equilibrium
Settling the robust learnability of mixtures of Gaussians
Cooperative asynchronous update of shared memory
Concurrent Composition Theorems for Differential Privacy
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Near-linear time decoding of Ta-Shma's codes via splittable regularity
When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One
Parallel algorithms for select and partition with noisy comparisons
Non-monotone submodular maximization under matroid and knapsack constraints
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems
Every planar graph is the intersection graph of segments in the plane: extended abstract
On Generalized Finite Automata and Unrestricted Generative Grammars
The recognition of Series Parallel digraphs
Fully-dynamic min-cut
On the fourier tails of bounded functions over the discrete cube
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
Symmetric Perceptrons, Number Partitioning and Lattices
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Free Groups and Regular Expressions
Probing Convex Polytopes
Finding short lattice vectors within mordell's inequality
Perfect Zero-Knowledge PCPs for #P
A tight bound on approximating arbitrary metrics by tree metrics
On the fractal behavior of TCP
Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model
On identity testing of tensors, low-rank recovery and compressed sensing
A quantum lovász local lemma
Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version)
Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008
Succinct Computational Secret Sharing
On the list decodability of random linear codes with large error rates
Fast convergence to Wardrop equilibria by adaptive sampling methods
Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications
Hardness of routing with congestion in directed graphs
On the Method of Approximations
Towards an Analysis of Local Optimization Algorithms
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Practical Loss-Resilient Codes
Monotone circuit lower bounds from resolution
An O(log n log log n) space algorithm for undirected st-connectivity
.879-approximation algorithms for MAX CUT and MAX 2SAT
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
An Efficient General Purpose Parallel Computer
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy
On the approximation resistance of balanced linear threshold functions
On strip packing With rotations
Log-space polynomial end-to-end communication
A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract)
Stability Results for Networks with Input and Output Blocking
Randomized dynamic graph algorithms with polylogarithmic time per operation
Pseudodeterministic constructions in subexponential time
Complexity of short Presburger arithmetic
Polyhedral clinching auctions and the adwords polytope
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997
Removing Additive Structure in 3SUM-Based Reductions
Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings
Matrix anti-concentration inequalities with applications
Inner product spaces for MinSum coordination mechanisms
Sum of Squares Lower Bounds from Pairwise Independence
Good Binary Quantum Codes with Transversal CCZ Gate
Logics for Probabilistic Programming (Extended Abstract)
A new analysis of differential privacy's generalization guarantees (invited paper)
Deterministic, near-linear ε -approximation algorithm for geometric bipartite matching
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA
Digital Disks and a Digital Compactness Measure
Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
Pebblings, Edgings, and Equational Logic
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
A Unified Framework for Light Spanners
Matroids and integrality gaps for hypergraphic steiner tree relaxations
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization
The all-or-nothing multicommodity flow problem
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Randomness-optimal unique element isolation, with applications to perfect matching and related problems
The power of deferral: maintaining a constant-competitive steiner tree online
Fault-Tolerant Quantum Computation With Constant Error
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms
Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines
Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
Faster Mixing via Average Conductance
Tight lower bounds for the online labeling problem
The art gallery problem is ∃ ℝ-complete
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
The Complexity of Optimization Problems
Dynamic set cover: improved algorithms and lower bounds
Generating random regular graphs
On the power of unique 2-prover 1-round games
Combinatorial Complexity of the Central Curve
Commitments to Quantum States
A Near Optimal Data Structure for a Type of Range Query Problem
Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
DecreaseKeys are expensive for external memory priority queues
Fully dynamic maximal independent set with sublinear update time
Finding, minimizing, and counting weighted subgraphs
Algorithms for subset selection in linear regression
Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract)
Subquadratic dynamic path reporting in directed graphs against an adaptive adversary
Reimer's inequality and tardos' conjecture
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA
On lattices, learning with errors, random linear codes, and cryptography
A New Composition Theorem for Learning Algorithms
Uncertainty principles, extractors, and explicit embeddings of l2 into l1
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
A (2+ε)-Approximation Algorithm for Metric k-Median
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017
Randomized and multipointer paging with locality of reference
Approximation techniques for utilitarian mechanism design
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING
Work-time-optimal parallel algorithms for string problems
A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column
Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem
Designing Programs That Check Their Work
Trace reconstruction with exp(O(n 1/3 )) samples
The randomized communication complexity of randomized auctions
Classical Simulation of Peaked Shallow Quantum Circuits
Continuous LWE
A Separator Theorem for Graphs with an Excluded Minor and its Applications
Implicit Representation of Graphs
Approximating minimum bounded degree spanning trees to within one of optimal
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
On the geometry of graphs with a forbidden minor
Improved Distributed Algorithms for Coloring and Network Decomposition Problems
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
On the solution-space geometry of random constraint satisfaction problems
The computational complexity of recognizing permutation functions
Online Algorithms for Selective Multicast and Maximal Dense Trees
The complexity of choosing an H-colouring (nearly) uniformly at random
Classes of Functions for Computing on Binary Trees (Extended Abstract)
Observations on Nondeterministic Multidimensional Iterative Arrays
Linear degree extractors and the inapproximability of max clique and chromatic number
Bootstrapping variables in algebraic circuits
Algorithms, games, and the internet
Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization
Approximate modularity revisited
Aggregating inconsistent information: ranking and clustering
Many-to-one packet routing on grids (Extended Abstract)
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n 1/2 - ε )-time
Hardness of approximate two-level logic minimization and PAC learning with membership queries
Does learning require memorization? a short tale about a long tail
Fast Approximation Algorithms for Multicommodity Flow Problems
Approximation Schemes for Euclidean k -Medians and Related Problems
An o(log 2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem
Quantum Cryptography in Algorithmica
Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines
New direct-product testers and 2-query PCPs
Fully homomorphic encryption using ideal lattices