Entity usage

This page lists pages that use the given entity (e.g. Q42). The list is sorted by descending page ID, so that newer pages are listed first.

Showing below up to 50 results in range #1 to #50.

Combinatorial Bernoulli factories: matchings, flows, and other polytopes: Label: en
A faster algorithm for solving general LPs: Label: en
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits: Label: en
Structure vs. randomness for bilinear maps: Label: en
Lower bounds for monotone arithmetic circuits via communication complexity: Label: en
Kronecker products, low-depth circuits, and matrix rigidity: Label: en
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma: Label: en
Fiat–Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge): Label: en
Indistinguishability obfuscation from circular security: Label: en
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity: Label: en
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE: Label: en
Continuous LWE: Label: en
Online stochastic matching, poisson arrivals, and the natural linear program: Label: en
A framework for dynamic matching in weighted graphs: Label: en
Fully dynamic approximation of LIS in polylogarithmic time: Label: en
Contextual search in the presence of irrational agents: Label: en
Improved dynamic algorithms for longest increasing subsequence: Label: en
Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization: Label: en
Decremental all-pairs shortest paths in deterministic near-linear time: Label: en
The randomized communication complexity of randomized auctions: Label: en
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma: Label: en
Towards tight bounds for spectral sparsification of hypergraphs: Label: en
A framework for quadratic form maximization over convex sets through nonconvex relaxations: Label: en
Robust testing of low dimensional functions: Label: en
Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances: Label: en
Almost optimal super-constant-pass streaming lower bounds for reachability: Label: en
Information theoretic limits of cardinality estimation: Fisher meets Shannon: Label: en
Optimal testing of discrete distributions with high probability: Label: en
Capacity lower bounds via productization: Label: en
A theory of universal learning: Label: en
Settling the robust learnability of mixtures of Gaussians: Label: en
VC dimension and distribution-free sample-based testing: Label: en
Algorithmic foundations for the diffraction limit: Label: en
Boosting simple learners: Label: en
Hardness of learning DNFs using halfspaces: Label: en
Stronger calibration lower bounds via sidestepping: Label: en
Adversarial laws of large numbers and optimal regret in online classification: Label: en
Fractionally log-concave and sector-stable polynomials: counting planar matchings and more: Label: en
Breaking the quadratic barrier for matroid intersection: Label: en
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests: Label: en
Support of closed walks and second eigenvalue multiplicity of graphs: Label: en
Deterministic mincut in almost-linear time: Label: en
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches: Label: en
Tree embeddings for hop-constrained network design: Label: en
Clan embeddings into trees, and low treewidth graphs: Label: en
Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time: Label: en
Vertex connectivity in poly-logarithmic max-flows: Label: en
Pseudodeterministic algorithms and the structure of probabilistic time: Label: en
Average-case hardness of NP from exponential worst-case hardness assumptions: Label: en
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost: Label: en