yusuke1997/dblp-id-title huggingface dataset:
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
On the Communication Complexity of Graph Properties
Optimal finger search trees in the pointer machine
Dynamic rectangular intersection with priorities
Sharp threshold and scaling window for the integer partitioning problem
Translating Recursion Equations into Flow Charts
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Heuristics for Weighted Perfect Matching
An information complexity approach to extended formulations
Efficient randomized DCAS
Constant-Factor EFX Exists for Chores
Undecidability on Quantum Finite Automata
Balanced allocations: the weighted case
Lower Bounds on the Complexity of Graph Properties
Evolving sets and mixin
Rapid sampling though quantum computing
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
Deterministic coding for interactive communication
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
The Chip Complexity of Binary Arithmetic
Simpler and better approximation algorithms for network design
When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks
Is There an Algebraic Proof for P != NC ? (Extended Abstract)
Quantum time-space tradeoffs for sorting
Low rank approximation and regression in input sparsity time
Relativized Questions Involving Probabilistic Algorithms
On the Lovász Theta function for Independent Sets in Sparse Graphs
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
The HOM problem is decidable
The Node Cost Measure for Embedding Graphs on the Planar Grid (Extended Abstract)
Communication preserving protocols for secure function evaluation
Imperfect Random Sources and Discrete Controlled Processes
Higher lower bounds on monotone size
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
XOR Lemmas for Communication via Marginal Information
Distinguishing tests for nondeterministic and probabilistic machines
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007
On the Boosting Ability of Top-Down Decision Tree Learning Algorithms
Circuits resilient to short-circuit errors
Smooth sensitivity and sampling in private data analysis
Stochastic contention resolution with short delays
Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon
On Approximability of Satisfiable k-CSPs: III
On quantum and probabilistic communication: Las Vegas and one-way protocols
Compression using efficient multicasting
Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece
Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version)
Quantum Information Complexity
Computational Learning Theory: Survey and Selected Bibliography
A generalization of permanent inequalities and applications in counting and optimization
Unconditional pseudorandom generators for low degree polynomials
Succinct Non-interactive Arguments of Proximity
Finding Extremal Polygons
A Model for Data in Motion
Parametric real-time reasoning
Approximate max-flow min-(multi)cut theorems and their applications
Data-streams and histograms
Sample-optimal and efficient learning of tree Ising models
Approximate polytope membership queries
Learnability can be independent of set theory (invited paper)
Probabilistic Tree Automata
Weighted low rank approximations with provable guarantees
Planar point sets determine many pairwise crossing segments
Quantum money from hidden subspaces
Biased dictionaries with fast insert/deletes
Inapproximability of the independent set polynomial in the complex plane
Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
A deterministic reduction for the gap minimum distance problem: [extended abstract]
Problems, Complete in "Average" Instance
Edge isoperimetry and rapid mixing on matroids and geometric Markov chains
A fast algorithm for computing steiner edge connectivity
Similarity estimation techniques from rounding algorithms
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem
On Approximability of Satisfiable k-CSPs: IV
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Optimal testing of discrete distributions with high probability
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Some Complexity Questions Related to Distributive Computing (Preliminary Report)
Algorithmic discrepancy beyond partial coloring
Hardness amplification proofs require majority
Changing base without losing space
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems
An Algorithm for the General Petri Net Reachability Problem
Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version)
The Decidability of Equivalence for Deterministic Finite-Turn Pushdown Automata
3.1 n - o ( n ) circuit lower bounds for explicit functions
Synchronization strings: explicit constructions, local decoding, and applications
Boosted sampling: approximation algorithms for stochastic optimization
Random Instances of a Graph Coloring Problem Are Hard
The invasiveness of off-line memory checking
Collusion-free protocols
Energy Consumption in VLSI Circuits (Preliminary Version)
Online and dynamic algorithms for set cover
Clustering mixture models in almost-linear time via list-decodable mean estimation
On the Complexity of the Extended String-to-String Correction Problem
On the Complexity of the Maximum Subgraph Problem
Tree-Size Bounded Alternation
Reducing path TSP to TSP
How tall is a tree?
Testing Polynomials which Are Easy to Compute (Extended Abstract)
Building a Complete Inverted File for a Set of Text Files in Linear Time
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Approximating Partition in Near-Linear Time
Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report)
Balanced metric labeling
The limits of buffering: a tight lower bound for dynamic membership in the external memory model
Comparative Complexity of Grammar Forms
Online server allocation in a server farm via benefit task systems
Node- and Edge-Deletion NP-Complete Problems
Tight Bounds on the Complexity of Parallel Sorting
Small Value Parallel Repetition for General Games
Work-competitive scheduling for cooperative computing with dynamic groups
Regression from dependent observations
Time and Space Efficient Deterministic Decoders
Subcubic algorithms for Gomory-Hu tree in unweighted graphs
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
How to rank with few errors
Contention resolution without collision detection
Knowledge on the average-perfect, statistical and logarithmic
Streaming symmetric norms via measure concentration
Inverting well conditioned matrices in quantum logspace
Kernel-based methods for bandit convex optimization
Maximizing determinants under partition constraints
How to Construct Random Unitaries
Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
Routing under balance
Constructing Disjoint Paths on Expander Graphs (Extended Abstract)
Sum-of-squares meets nash: lower bounds for finding any equilibrium
Privacy amplification with asymptotically optimal entropy loss
Affiliation networks
Intercalation Theorems for Tree Transducer Languages
On approximating functions of the singular values in a stream
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings
Strong average-case lower bounds from non-trivial derandomization
Polynomial Time Reducibility
An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version)
The Theory of Signature Testing for VLSI
Bilipschitz snowflakes and metrics of negative type
A spectral technique for coloring random 3-colorable graphs (preliminary version)
Some Optimal Inapproximability Results
A strongly polynomial algorithm for generalized flow maximization
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA
Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract)
Efficient randomized distributed coloring in CONGEST
On optimal slicing of parallel programs
Optimal suffix selection
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Directed spanners via flow-based linear programs
An optimal space lower bound for approximating MAX-CUT
Space complexity in propositional calculus
On the convergence of regret minimization dynamics in concave games
A New Solution to the Critical Section Problem
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998
Data Graphs and Addressing Schemes: Extended Abstract
Verifying and decoding in constant depth
A polynomial lower bound on adaptive complexity of submodular maximization
Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation
On the geometry of differential privacy
An SDP-based algorithm for linear-sized spectral sparsification
Determining Graph Properties from Matrix Representations
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract)
Exponential Separation of Information and Communication for Boolean Functions
The Complexity of Reasoning about Knowledge and Time: Extended Abstract
A Probabilistic Dynamic Logic
Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes
Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
Solving large optimization problems using spectral graph theory
One-Way Functions and Pseudorandom Generators
Discrepancy minimization via a self-balancing walk
Nearly optimal sparse fourier transform
Some Connections between Mathematical Logic and Complexity Theory
How Good is the Goemans-Williamson MAX CUT Algorithm?
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract)
Ham-Sandwich Cuts in R^d
Satisfiability of equations in free groups is in PSPACE
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Digital Straightness and Convexity (Extended Abstract)
Computational Sample Complexity and Attribute-Efficient Learning
Symmetry breaking for suffix tree construction
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems
Learning with attribute costs
Fast FPT-approximation of branchwidth
On Sorting Strings in External Memory (Extended Abstract)
Non-malleable secret sharing
On average distortion of embedding metrics into the line and into L1
New hardness results for planar graph problems in p and an algorithm for sparsest cut
List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel
Lines in Space-Combinatorics, Algorithms and Applications
Max flows in O(nm) time, or better
Deterministic massively parallel connectivity
Approximate distance oracles with constant query time
Flow time scheduling and prefix Beck-Fiala
Minimizing Flow-Time on Unrelated Machines
On the fault tolerance of the butterfly
Rotation Distance, Triangulations, and Hyperbolic Geometry
Quantum Fourier Sampling Simplified
Lower Bounds on the Size of Boolean Formulas: Preliminary Report
On optimal single-item auctions
Minimum k-way cuts via deterministic greedy tree packing
Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues
Gentle measurement of quantum states and differential privacy
Wait-free consensus with infinite arrivals
Tight bounds for monotone switching networks via fourier analysis
On the Fourier spectrum of monotone functions (Extended Abstract)
Receipt-free secret-ballot elections (extended abstract)
Explicit Two-Sided Unique-Neighbor Expanders
Constructing Evolutionary Trees in the Presence of Polymorphic Characters
Impossibility results for recycling random bits in two-prover proof systems
Non-malleability amplification
A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria
Secure hypergraphs: privacy from partial broadcast (Extended Abstract)
Constant-round non-malleable commitments from any one-way function
Directed flow-augmentation
Algebrization: a new barrier in complexity theory
On real Turing machines that toss coins
Definability in Dynamic Logic
The small-world phenomenon: an algorithmic perspective
Sampling Balanced Forests of Grids in Polynomial Time
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
Allocating Bandwidth for Bursty Connections
Constant-Round Arguments from One-Way Functions
Tree-Oriented Proofs of Some Theorems on Context-Free and Indexed Languages
Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract)
Effective Noether Irreducibility Forms and Applications (Extended Abstract)
On the convergence of Newton's method for monotone systems of polynomial equations
An algorithmic characterization of multi-dimensional mechanisms
Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary)
Computing with Faulty Arrays
The Lane Tracing Algorithm for Constructing LR(k) Parsers
Robustness Implies Privacy in Statistical Estimation
Optimal parallel string algorithms: sorting, merging and computing the minimum
On the Complexity of Nash Equilibria in Anonymous Games
Compression of quantum multi-prover interactive proofs
On the Pagenumber of Planar Graphs
How to Distribute a Dictionary in a Complete Network
Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract)
Cutting triangular cycles of lines in space
Locality vs Quantum Codes
A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
Zero-one frequency laws
The complexity of maximal constraint languages
Estimating normalizing constants for log-concave distributions: algorithms and lower bounds
Extending continuous maps: polynomiality and undecidability
Computing the Volume Is Difficult
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
Online stochastic matching, poisson arrivals, and the natural linear program
Repairing Reed-solomon codes
TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract)
Optimal Algorithms for Approximate Clustering
Computational Complexity and Numerical Stability
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
A faster algorithm for solving general LPs
Multicut is FPT
Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs
One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation
Delegation for bounded space
Making polynomials robust to noise
Dynamic Algebras and the Nature of Induction
Optimal terminal dimensionality reduction in Euclidean space
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Lower Bounds for Distributed Coin-Flipping and Randomized Consensus
Reasoning about Knowledge and Time in Asynchronous Systems
Complexity of Formal Translations and Speed-Up Results
Six Candidates Suffice to Win a Voter Majority
Nearest Neighbor Queries in Metric Spaces
A Model for Hierarchical Memory
A 3-query PCP over integers
The computational power of optimization in online learning
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
On Classes of Computable Functions
Improved analysis of higher order random walks and applications
Approximating Total Flow Time on Parallel Machines
Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Fooling Gaussian PTFs via local hyperconcentration
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Expanders, Sorting in Rounds and Superconcentrators of Limited Depth
Pseudo-random Generation from one-way functions (Extended Abstracts)
Non-Interactive and Non-Malleable Commitment
Addition is exponentially harder than counting for shallow monotone circuits
A theory of parameterized pattern matching: algorithms and applications
The menu-size complexity of revenue approximation
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Parallel repetition: simplifications and the no-signaling case
Computing with Tangles
Anomaly Hierarchies of Mechanized Inductive Inference
Competitive Distributed Job Scheduling (Extended Abstract)
Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract)
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA
The limitations of optimization from samples
A learning theory approach to non-interactive database privacy
Efficient routing in all-optical networks
The effect of collusion in congestion games
Edge connectivity augmentation in near-linear time
FPTAS for #BIS with Degree Bounds on One Side
Extractors and pseudo-random generators with optimal seed length
Testing Isomorphism on Cone Graphs (Extended Abstract)
Dictionary matching and indexing with errors and don't cares
Rounding Large Independent Sets on Expanders
Towards 3-query locally decodable codes of subexponential length
Oblivious Transfer and Polynomial Evaluation
Combinatorial Bernoulli factories: matchings, flows, and other polytopes
Polynomial-Time PIT from (Almost) Necessary Assumptions
New High Dimensional Expanders from Covers
Searching dynamic point sets in spaces with bounded doubling dimension
Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract)
Regular resolution lower bounds for the weak pigeonhole principle
Learning restricted Boltzmann machines via influence maximization
Infinite randomness expansion with a constant number of devices
The complexity of analytic tableaux
Weak zero-knowledge beyond the black-box barrier
Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance
Modular Coloring Formulas Are Hard for Cutting Planes Proofs
Approximating min-sum k -clustering in metric spaces
Minimizing Stall Time in Single and Parallel Disk Systems
Improved Quantum data analysis
Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version)
Network Unreliability in Almost-Linear Time
The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial
Some Algebraic and Geometric Computations in PSPACE
High Rate Multivariate Polynomial Evaluation Codes
Checking approximate computations over the reals
Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity
On the complexity of verifiable secret sharing and multiparty computation
Linearity and Unprovability of Set Union Problem Strategies
A polynomial restriction lemma with applications
Small-size epsilon-nets for axis-parallel rectangles and boxes
Testing Support Size More Efficiently Than Learning Histograms
Information theoretic limits of cardinality estimation: Fisher meets Shannon
Optimal online scheduling of parallel jobs with dependencies
Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract
Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials
An optimal sdp algorithm for max-cut, and equally optimal long code tests
Translational Polygon Containment and Minimal Enclosure using Linear Programming Based Restriction
Fast Algorithms for N-Dimensional Restrictions of Hard Problems
Private selection from private candidates
Efficiently learning halfspaces with Tsybakov noise
Algorithmic stability for adaptive data analysis
A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem
The Expressive Power of Voting Polynomials
On the round complexity of covert computation
Universally utility-maximizing privacy mechanisms
An Optimal Solution to a Wire-Routing Problem (Preliminary Version)
The Power of Multi-step Vizing Chains
A constant factor approximation for the single sink edge installation problems
The price of privacy and the limits of LP decoding
Finding Patterns Common to a Set of Strings (Extended Abstract)
All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust
Communication lower bounds via critical block sensitivity
More general completeness theorems for secure two-party computation
A deterministic algorithm for the MST problem in constant rounds of congested clique
Quantum State Obfuscation from Classical Oracles
Local concentration inequalities and Tomaszewski's conjecture
Direct Product Results and the GCD Problem, in Old and New Communication Models
Logarithmic hardness of the directed congestion minimization problem
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm
Approximations for the disjoint paths problem in high-diameter planar networks
Towards a proof of the 2-to-1 games conjecture?
Improved dynamic algorithms for longest increasing subsequence
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract)
Isomorphism for Graphs Embeddable on the Projective Plane
Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games
Using petal-decompositions to build a low stretch spanning tree
Beating Brute Force for Compression Problems
Loop Schemata
Deterministic Õ (nm) Time Edge-Splitting in Undirected Graphs
A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
Entropy and Sorting
Exponential Lower Bounds for Restricted Monotone Circuits
Protecting Computations against Continuous Bounded-Communication Leakage
Iterated Pushdown Automata and Complexity Classes
Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers
Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract)
Excellent codes from modular curves
Strong ETH holds for regular resolution
Faster parallel algorithm for approximate shortest path
Fast perfection-information leader-election protocol with linear immunity
Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
A Technique for Speeding Up LR(k) Parsers
Dynamic low-stretch trees via dynamic low-diameter decompositions
Exact learning of random DNF over the uniform distribution
A spectral approach to network design
Circuit minimization problem
Circuit lower bounds for Merlin-Arthur classes
Circuits resilient to additive attacks with applications to secure computation
Some Consequences of the Existence of Pseudorandom Generators
Parallel Repetition for 3-Player XOR Games
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme
Communication Complexity of Secure Computation (Extended Abstract)
Tree Evaluation Is in Space O(log n · log log n)
A Minimum Area VLSI Network for O(log n) Time Sorting
Markov chains, computer proofs, and average-case analysis of best fit bin packing
Random Permutations using Switching Networks
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009
Cryptographic hardness of distribution-specific learning
The Round Complexity of Secure Protocols (Extended Abstract)
Sparse nonnegative convolution is equivalent to dense nonnegative convolution
Greedy Algorithms for Steiner Forest
A High Dimensional Goldreich-Levin Theorem