yusuke1997/dblp-id-title huggingface dataset:
An Optimal Lower Bound on the Number of Total Operations to Compute 0-1 Polynomials over the Field of Complex Numbers
Feature Purification: How Adversarial Training Performs Robust Deep Learning
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners
How Asymmetry Helps Load Balancing
The Geometry of Coin-Weighing Problems
No Occurrence Obstructions in Geometric Complexity Theory
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
On the Unique Games Conjecture
Graph Isomorphism is in SPP
PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring
Simulated Annealing for Graph Bisection
Polylogarithmic Independence Can Fool DNF Formulas
Probabilistic Communication Complexity (Preliminary Version)
Machtey Award
Fast Management of Permutation Groups
(2 + epsilon)-Sat Is NP-Hard
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles
An O(1)-Approximation for Minimum Spanning Tree Interdiction
A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs
River Routing Every Which Way, but Loose (Extended Abstract)
A Sampling Lovász Local Lemma for Large Domain Sizes
Lockable Obfuscation
Testing Permutation Polynomials (Extended Abstract)
Efficient Average-Case Algorithms for the Modular Group
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain
Decomposition of sequential machines
The Power of Asymmetry in Constant-Depth Circuits
Protocols for Asymmetric Communication Channels
On the Optimality of the Dimensionality Reduction Method
Protocols and Impossibility Results for Gossip-Based Communication Mechanisms
Standard Minimum Transition Time Secondary Assignments for Asynchronous Circuits
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds
Settling the Polynomial Learnability of Mixtures of Gaussians
Polytopes, Permanents and Graphs with Large Factors
Tradeoffs for small-depth Frege proofs
Informational Substitutes
Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics
Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
PPP-Completeness with Connections to Cryptography
Static Dictionaries on AC 0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient
Generating k-Independent Variables in Constant Time
Polynomial End-To-End Communication (Extended Abstract)
Real Time Counter Machines (Preliminary Version)
The Implicit Graph Conjecture is False
Interior-point methods on manifolds: theory and applications
Clustering Data Streams
Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version)
Automatic Theorem-Proving and the Decision Problem
Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees
Parsing for Structural Editors (Extended Abstract)
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Efficient Self-Embedding of Butterfly Networks with Random Faults
Las Vegas algorithms for matrix groups
Tight Fault Locality (Extended Abstract)
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
An Upper Bound on the Number of Planar k-Sets
Extractors for Near Logarithmic Min-Entropy
On the Decision Tree Complexity of the Shortest Path Problems
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs
A Unified Geometric Approach to Graph Separators
Efficient and Explicit Coding for Interactive Communication
A Quantum Advantage for a Natural Streaming Problem
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice
On the Insecurity of Parallel Repetition for Leakage Resilience
An Efficient Parallel Garbage Collection System and Its Correctness Proof
Approximation Algorithms for Unique Games
Sample-efficient learning of quantum many-body systems
On the Number of P-Isomorphism Classes of NP-Complete Sets
Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)
On Threshold Circuits for Parity
Graph Grammars and Global Program Data Flow Analysis
Spectral Approaches to Nearest Neighbor Search
On the Structure of Complete Sets: Almost Everywhere Complexity and Infinitely Often Speedup
Tree-depth and the Formula Complexity of Subgraph Isomorphism
Three-Player Entangled XOR Games Are NP-Hard to Approximate
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
A Fast Algorithm for Single Processor Scheduling
Approximation Schemes for Maximum Weight Independent Set of Rectangles
imits on the Power of Quantum Statistical Zero-Knowledge
(Data) STRUCTURES
On the Relation between Descriptional Complexity and Algorithmic Probability
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Separating the Power of Monotone Span Programs over Different Fields
On Endomorphisms and Congruences of Automata
Automorphism Groups and Quotients of Strongly Connected Automata and Monadic Algebras
Antiparallel control logic
Pseudorandomness from Shrinkage
A Circuit-Size Lower Bound
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture
Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time
Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs
On the Quantum Query Complexity of Local Search in Two and Three Dimensions
Biased 2-3 Trees
The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
Models of Program Logics
A Combinatorial Limit to the Computing Power of V.L.S.I. Circuits (Extended Abstract)
Stoquastic PCP vs. Randomness
Shrinkage of De Morgan Formulae by Spectral Techniques
Learning Conjunctions of Horn Clauses (Extended Abstract)
Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets
Bilateral threshold nets (extended summary)
Length of Predicate Calculus Formulas as a New Complexity Measure
An Improved Bound for Weak Epsilon-Nets in the Plane
An optimal randomized online algorithm for reordering buffer management
Extracting Correlations
Two Contributions to Redundancy Theory
Minimal Degrees for Honest Polynomial Reducibilities
Broadcasting Algorithms in Radio Networks with Unknown Topology
Lower Bounds for (MOD p - MOD m) Circuits
Perfect Lp Sampling in a Data Stream
Testing Hereditary Properties of Ordered Graphs and Matrices
Making Nondeterminism Unambiguous
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space
On Decomposition of Relational Databases
On the Approximability of Trade-offs and Optimal Access of Web Sources
Coin Flipping with Constant Bias Implies One-Way Functions
Preserving Order in a Forest in less than Logarithmic Time
Quantum Speed-Up of Markov Chain Based Algorithms
Sublinear Optimization for Machine Learning
Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back
The Data Stream Space Complexity of Cascaded Norms
A four-megacycle, 24-bit checked binary adder
The Analysis of a List-Coloring Algorithm on a Random Graph
Sum-of-Squares Lower Bounds for Sparse Independent Set
Towards Separating Computational and Statistical Differential Privacy
On a Class of Totally Unimodular Matrices
The Incompletely-Specified Finite-State Stochastic Sequential Machine Equivalence and Reduction
Exploiting Locality for Data Management in Systems of Limited Bandwidth
Local Global Tradeoffs in Metric Embeddings
Clique is Hard to Approximate Within n 1-epsilon
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Faster Approximate Pattern Matching: A Unified Approach
Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract)
Computing Irreducible Representations of Finite Groups
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability
Lower Bounds on Information Transfer in Distributed Computations
Long Tours and Short Superstrings (Preliminary Version)
27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986
A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions
Lower Bounds from Complex Function Theory
Optimal Suffix Tree Construction with Large Alphabets
A Time Hierarchy Theorem for the LOCAL Model
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
Efficient Parallel Algorithms for Tree-Decomposition and Related Problems
Truthful and Near-Optimal Mechanism Design via Linear Programming
Explicit Constructions of Linear Size Superconcentrators
Formulas Resilient to Short-Circuit Errors
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem
One-Way Stack Automata (Extended Abstract)
Randomized Geometric Algorithms and Pseudo-Random Generators (Extended Abstract)
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2
Better lossless condensers through derandomized curve samplers
Efficient Interactive Coding against Adversarial Noise
The Operator Gap
The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)
Nested Graph Dissection and Approximation Algorithms
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Testing Monotonicity
The Communication Complexity of Approximating Matrix Rank
Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources
Algorithmic Aspects of Protein Structure Similarity
Renamings in Program Schemas (Extended Abstract)
Faster Matrix Multiplication via Asymmetric Hashing
A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
Specified Precision Polynomial Root Isolation is in NC
A model of concurrent database transactions (summary)
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems
A Recursive Greedy Algorithm for Walks in Directed Graphs
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs
Sparsifying Sums of Norms
Binary Codes with Resilience Beyond 1/4 via Interaction
Improved Algorithms for Graph Four-Connectivity
Separator-Based Strategies for Efficient Message Routing (Preliminary Version)
Elections Can be Manipulated Often
Derivation-Bounded Languages
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Tracking the Best Disjunction
Combinatorial feature selection problems
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$
Recursive Schemes, Algebraic Trees and Deterministic Languages
Probabilistically Checkable Proofs with Low Amortized Query Complexity
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time
Extractors and Secret Sharing Against Bounded Collusion Protocols
Computing in Solvable Matrix Groups
Learning Graphical Models Using Multiplicative Weights
Twin-width I: tractable FO model checking
Algebraic Decompositions of Non-Convex Polyhedra
Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract)
On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates
Logarithmic Depth Circuits for Algebraic Functions
Lower Bounds for Polynomial Evaluation and Interpolation Problems
A Tale of Two Dimensional Bin Packing
Constant Depth Circuits, Fourier Transform, and Learnability
A Topological Approach to Evasiveness
On One-Dimensional Quantum Cellular Automata
Hardness Results for Structured Linear Systems
The Complexity of Distributions
A Time-Luck Tradeoff in Cryptography
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Derandomization from Algebraic Hardness: Treading the Borders
A deterministic near-linear time approximation scheme for geometric transportation
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
Universal Emulations with Sublogarithmic Slowdown
How to Construct Quantum Random Functions
First Price Auction is 1 - 1 /e 2 Efficient
Hardness of Approximating the Shortest Vector Problem in High L p Norms
Explicit Subspace Designs
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications
Concurrent Non-Malleable Zero Knowledge
Generalized Uniformity Testing
An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton
Beyond Tree Embeddings - a Deterministic Framework for Network Design with Deadlines or Delay
An ETH-Tight Exact Algorithm for Euclidean TSP
The Parameterized Complexity of Counting Problems
Extracting Randomness from Samplable Distributions, Revisited
Relativized Circuit Complexity
Dynamic Segment Intersection Search with Applications
Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
Breaking the Three Round Barrier for Non-malleable Commitments
Constrained Submodular Maximization: Beyond 1/e
Polynomials with 0-1 Coefficients that Are Hard to Evaluate
Efficient Unitary Designs from Random Sums and Permutations
Matrix Completion in Almost-Verification Time
On the Ability to Cover LR(k) Grammars with LR(1), SLR(1), and (1,1) Bounded-Context Grammars
A Lower Bound for the Dictionary Problem under a Hashing Model
On the Decomposition of Asynchronous Systems
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Quantum Eigenvalue Processing
P-Complete Problems and Approximate Solutions
stateQIP = statePSPACE
Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations
Beyond the Flow Decomposition Barrier
The General Synthesis Problem for Asynchronous Digital Networks
On the Decidability of Self-Assembly of Infinite Ribbons
(De)randomized Construction of Small Sample Spaces in \calNC
Classical Lower Bounds from Quantum Upper Bounds
Optimal Quantum Strong Coin Flipping
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Mechanism Design via Differential Privacy
Two-sided finite-state transductions (abbreviated version)
Efficient Algorithms for Simple Matroid Intersection Problems
Weak Adversaries for the k-Server Problem
Hardness vs. Randomness (Extended Abstract)
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
Irreducible Decompositions of Transformation Graphs by Assignment Techniques
Setting Parameters by Example
Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
Communication Complexity of Algebraic Computation (Extended Abstract)
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions
Holographic Algorithms (Extended Abstract)
A Chernoff bound for random walks on expander graphs
Leakage-Resilient Secret Sharing Against Colluding Parties
Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem
Minimum Cuts in Directed Graphs via Partial Sparsification
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow
Spectral Analysis of Random Graphs with Skewed Degree Distributions
On the Power of Preconditioning in Sparse Linear Regression
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings
Cuts, Trees and l 1 -Embeddings of Graphs
Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments
Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version)
54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October, 26-29, 2013
How Bad is Forming Your Own Opinion?
Interior point methods are not worse than Simplex
Fast Approximation Algorithms for Knapsack Problems
Automating Resolution is NP-Hard
Extracting Randomness via Repeated Condensing
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
PAC Learning with Irrelevant Attributes
Near-Optimal Parallel Prefetching and Caching
Wafer-Scale Integration of Systolic Arrays (Extended Abstract)
Arc-Disjoint Paths in Expander Digraphs
Testing Graph Clusterability: Algorithms and Lower Bounds
Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates
Mixture Selection, Mechanism Design, and Signaling
On the Power of Quantum Computation
On the Combinatorial and Topological Complexity of a Single Cell
Take a Walk, Grow a Tree (Preliminary Version)
Dynamic Perfect Hashing: Upper and Lower Bounds
Deterministic Computation of the Frobenius Form
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
A Concrete Security Treatment of Symmetric Encryption
Improved Bounds on Planar k-sets and k-levels
Computing Maximum Flow with Augmenting Electrical Flows
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)
The Synthesis of Finite State Syntax Directed Top-Down and Bottom-Up Transducers
Quantum SDP-Solvers: Better Upper and Lower Bounds
Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
Towards Sharp Inapproximability For Any 2-CSP
Nearly Tight Bounds on the Learnability of Evolution
Shortest Paths without a Map, but with an Entropic Regularizer
The Complexity of Some Non-Classical Logics
Capacity of Neural Networks for Lifelong Learning of Composable Tasks
Recharging Bandits
Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere
On ACC and Threshold Circuits
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
Negative-Weight Single-Source Shortest Paths in Near-linear Time
The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e
Computation by Multi-Head Finite Automata
On the Nisan-Ronen conjecture
Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet is Sigma_2^P-Complete
Halting Space-Bounded Computations
Synthesis of Multiple Sequential Machines
Concurrent Zero Knowledge with Logarithmic Round-Complexity
Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction
Polynomial-Time Pseudodeterministic Construction of Primes
How to Garble Arithmetic Circuits
Learning Multi-Item Auctions with (or without) Samples
The Online Submodular Assignment Problem
Quantum soundness of testing tensor codes
Models for the Compressible Web
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics
Strongly History-Independent Storage Allocation: New Upper and Lower Bounds
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds
On the Hardness of Being Truthful
Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time
Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract)
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
Quantum Advantage with Noisy Shallow Circuits in 3D
A Counterexample to Strong Parallel Repetition
Algebraic Computation Trees in Characteristi p>0 (Extended Abstract)
Datalog vs. First-Order Logic
The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication
Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Balanced Allocations: The Heavily Loaded Case with Deletions
Products and Help Bits in Decision Trees
On Clustering Induced Voronoi Diagrams
The Matching Problem in General Graphs Is in Quasi-NC
Sparse random hypergraphs: Non-backtracking spectra and community detection
Robust Estimators in High Dimensions without the Computational Intractability
A Direct Dynamic Solution to Range Search and Related Problems for Product Regions
Deterministic Small Vertex Connectivity in Almost Linear Time
Highly Fault-Tolerant Parallel Computation (extended abstract)
Higher Cell Probe Lower Bounds for Evaluating Polynomials
Satisfiability of Word Equations with Constants is in PSPACE
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes
Towards an Optimal Method for Dynamic Planar Point Location
A Sublinear Time Approximation Scheme for Clustering in Metric Spaces
New techniques for designing speed independent control logic
Drawing Graphs in the Plane with High Resolution
Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract)
Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method
A Brief Look at Pairings Based Cryptography
Effective Computation over the Real Numbers
Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction
Intrusion-Resilient Secret Sharing
Explicit Exclusive Set Systems with Applications to Broadcast Encryption
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes
16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975
Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces
Perspectives on Database Theory
Maximizing Non-Monotone Submodular Functions
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
Rounding Parallel Repetitions of Unique Games
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
Deterministic Communication vs. Partition Number
On Learning Mixtures of Heavy-Tailed Distributions
Equivalence Problems in Monadic Recursion Schemes
Talagrand's Convolution Conjecture on Gaussian Space
A lower bound on Rado's sigma function for binary Turing machines
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
Minimum Bounded Degree Spanning Trees
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes
Synthesis of Asynchronous Sequential Circuits with Master-Slave Subcircuits
Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Cryptography against Continuous Memory Attacks
On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract)
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Verifiable Quantum Advantage without Structure