Learnability in Valiant's model holds exactly when positive samples admit poly-size adaptive query-compression certification, strictly between PAC and query-free variants, with a poly(d) sample/query algorithm for d-dimensional halfspaces.
hub Canonical reference
A Geometric Heuristic for Rectilinear Crossing Minimization
Canonical reference. 78% of citing Pith papers cite this work as background.
62
Pith papers citing it
Background
78% of classified citations
hub tools
citation-role summary
background 8
other 1
citation-polarity summary
representative citing papers
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
Under ETH, no f(k) n^{o(k/log k)}-time algorithm can approximate k-permutation pattern counts within n^{(1/2-ε)k} factor, matching exact-counting hardness.
Every graph contains k vertex-disjoint cycles of distinct lengths or has a set of O(k^6 polylog(k)) vertices whose removal leaves at most k-1 cycle lengths.
The number of vertices in order-k abstract color Voronoi diagrams of n sites with m colors is at most 4k(n−k)−2n, proved via colorful Clarkson–Shor and tight bounds on circular sequences of colored permutations.
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.
A null-field continuation of force-free electrodynamics, with geodesic principal null directions, is introduced and shown to match 1D PIC simulations after loss of magnetic dominance in Alfvén wave collisions and type-changing solutions.
The parareal algorithm is shown to converge linearly for semilinear parabolic PDEs with H^2 initial data by using stable rational approximations and first-order linearization as coarse propagators, with a sharp convergence factor estimate.
Presents a quantum soft PCA framework with Fermi-Dirac filter for principal subspace scoring without eigenvector recovery, claiming dimension-independent sample complexity O(η^{-2}).
NeighborDiv detects graph anomalies via variance of inter-neighbor feature similarities under a new Neighbor-to-Neighbor Diversity Paradigm, achieving SOTA results with zero volatility in zero-shot cross-domain settings.
Proves max eigenvalue of level-k Kikuchi graph Laplacian is at most m+k for any graph with m edges, confirming conjectures and giving 0.614 approx ratio for Quantum Max Cut.
Deciding whether a graph admits a min-1-planar drawing is NP-hard.
QKLA achieves quadratic query-complexity improvement for clipped KL estimation, yielding 2.7-7.4x fewer oracle queries than classical methods when embedded in the PC causal-discovery algorithm at moderate precision.
New algorithms compute Hom spaces for poset representations in O(n^4 (thick(Y) + thick(Omega^1 Y))^2) time using a uniqueness result for lifts, plus a classical O(n^3 thick(Y)^3) method, both improving on O(n^6) and strengthening AIDA for multiparameter persistence.
Relativistic continuous matrix product states yield competitive variational approximations to ground state energies and observables in the phi^4, Sine-Gordon, and Sinh-Gordon models, including strongly coupled regimes.
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
Frank-Wolfe iterates for monotone variational inequalities converge asymptotically to the solution set under vanishing nonsummable step sizes, with the gap vanishing and unique convergence in the strongly monotone case.
An analog of Cauchy's surface area formula is established for Funk geometry on a convex body K using Holmes-Thompson area and central projections, reducing to a weighted vertex sum for polytopes and yielding a generalized Crofton formula.
In dynamic Stackelberg games with mid-game belief updates, assuming an incorrect follower best-response model can yield strictly lower leader cost than knowing the true model.
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
Central limit theorems are established for SAA value functions in finite-horizon stochastic optimal control via an abstract limit theorem for stochastic backward recursions, yielding recursive asymptotic variance formulas under unique optimal policies.
A Hermite-like basis minimizes neighbor data access in matrix-free DG SIP operators to one value and one derivative per neighbor on hexahedral elements via Jacobi roots and tensor products.
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
citing papers explorer
-
What is Learnable in Valiant's Theory of the Learnable?
Learnability in Valiant's model holds exactly when positive samples admit poly-size adaptive query-compression certification, strictly between PAC and query-free variants, with a poly(d) sample/query algorithm for d-dimensional halfspaces.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
The Presort Hierarchy for Geometric Problems
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
-
Inapproximability of Counting Permutation Patterns
Under ETH, no f(k) n^{o(k/log k)}-time algorithm can approximate k-permutation pattern counts within n^{(1/2-ε)k} factor, matching exact-counting hardness.
-
An Erd\H{o}s-P\'osa theorem for cycles and faces of distinct lengths
Every graph contains k vertex-disjoint cycles of distinct lengths or has a set of O(k^6 polylog(k)) vertices whose removal leaves at most k-1 cycle lengths.
-
Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations
The number of vertices in order-k abstract color Voronoi diagrams of n sites with m colors is at most 4k(n−k)−2n, proved via colorful Clarkson–Shor and tight bounds on circular sequences of colored permutations.
-
Practical Linear-Time Computation of Smallest Suffixient Sets
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.
-
Continuation of Force-Free Electrodynamics upon the loss of magnetic dominance
A null-field continuation of force-free electrodynamics, with geodesic principal null directions, is introduced and shown to match 1D PIC simulations after loss of magnetic dominance in Alfvén wave collisions and type-changing solutions.
-
Linear Convergence of Parareal Algorithm for Semilinear Parabolic Equations
The parareal algorithm is shown to converge linearly for semilinear parabolic PDEs with H^2 initial data by using stable rational approximations and first-order linearization as coarse propagators, with a sharp convergence factor estimate.
-
Quantum principal component analysis without eigenvector recovery
Presents a quantum soft PCA framework with Fermi-Dirac filter for principal subspace scoring without eigenvector recovery, claiming dimension-independent sample complexity O(η^{-2}).
-
NeighborDiv: Training-free Zero-shot Generalist Graph Anomaly Detection via Neighbor Diversity
NeighborDiv detects graph anomalies via variance of inter-neighbor feature similarities under a new Neighbor-to-Neighbor Diversity Paradigm, achieving SOTA results with zero volatility in zero-shot cross-domain settings.
-
Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
Proves max eigenvalue of level-k Kikuchi graph Laplacian is at most m+k for any graph with m edges, confirming conjectures and giving 0.614 approx ratio for Quantum Max Cut.
-
Min-1-Planarity is NP-Hard
Deciding whether a graph admits a min-1-planar drawing is NP-hard.
-
Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence
QKLA achieves quadratic query-complexity improvement for clipped KL estimation, yielding 2.7-7.4x fewer oracle queries than classical methods when embedded in the PC causal-discovery algorithm at moderate precision.
-
Computing Homomorphisms of Poset Representations with Applications to Multiparameter Persistence
New algorithms compute Hom spaces for poset representations in O(n^4 (thick(Y) + thick(Omega^1 Y))^2) time using a uniqueness result for lifts, plus a classical O(n^3 thick(Y)^3) method, both improving on O(n^6) and strengthening AIDA for multiparameter persistence.
-
Some progress on the use of the variational method in quantum field theory
Relativistic continuous matrix product states yield competitive variational approximations to ground state energies and observables in the phi^4, Sine-Gordon, and Sinh-Gordon models, including strongly coupled regimes.
-
Offline Local Search for Online Stochastic Bandits
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
-
Convergence of the Frank-Wolfe Algorithm for Monotone Variational Inequalities
Frank-Wolfe iterates for monotone variational inequalities converge asymptotically to the solution set under vanishing nonsummable step sizes, with the gap vanishing and unique convergence in the strongly monotone case.
-
Cauchy's Surface Area Formula in the Funk Geometry
An analog of Cauchy's surface area formula is established for Funk geometry on a convex body K using Holmes-Thompson area and central projections, reducing to a weighted vertex sum for polytopes and yielding a generalized Crofton formula.
-
When the Correct Model Fails: The Optimality of Stackelberg Equilibria with Follower Intention Updates
In dynamic Stackelberg games with mid-game belief updates, assuming an incorrect follower best-response model can yield strictly lower leader cost than knowing the true model.
-
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
-
Central Limit Theorems for Sample Average Approximations in Stochastic Optimal Control
Central limit theorems are established for SAA value functions in finite-horizon stochastic optimal control via an abstract limit theorem for stochastic backward recursions, yielding recursive asymptotic variance formulas under unique optimal policies.
-
A Hermite-like basis for faster matrix-free evaluation of interior penalty discontinuous Galerkin operators
A Hermite-like basis minimizes neighbor data access in matrix-free DG SIP operators to one value and one derivative per neighbor on hexahedral elements via Jacobi roots and tensor products.
-
Finding irrelevant vertices in linear time on bounded-genus graphs
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
-
Sublinear data structures for short Fr\'echet queries
Approximate distance oracles and ANN structures for short Fréchet queries on curves achieve space O((k log(1/ε) ε^{-d})^k) independent of input size N with O(k^2) query time.
-
Optimal Sparsifiers for Abelian Cayley Graphs
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
-
ResiPhy-MDNF: A Residual-Based Physics-Aware Multilevel Discrete Neural Field Framework for PDE-Constrained Inverse Problems
A per-instance learned graph-network transfer between coarse and fine discrete-field optimizations improves Darcy and EIT coefficient reconstructions without surrogates or pretraining.
-
Bayesian Poisson-Randomized Gamma Tensor Factorization with Application to International Trade Flows
A Bayesian CP tensor factorization model with Poisson rate for occurrence and conditional Gamma for magnitude, with slice-specific dispersion, applied to 60 million international trade flows to recover multiway dependencies.
-
QnRL: Quantum-Native Reinforcement Learning
QnRL is a distributional quantum RL framework that distills conditional action policies from moments of quantum generative models in Hilbert space via the QuAK algorithm, reporting higher scores and fewer parameters than baselines.
-
Everywhere Learning: Artificial Intelligence with Pointwise Constraints
Everywhere learning trains AI to meet pointwise loss constraints almost surely, backed by approximate duality theory for generalization and L1 regularization on relaxations.
-
A General Recipe for Parameter-Free Nonconvex Optimization via Higher-Order Regularization
A general framework for parameter-free smooth nonconvex optimization via higher-order regularization yields algorithms with optimal complexity bounds without prior parameter knowledge.
-
History-aware adaptive reduced-order models via incremental singular value decomposition
An iSVD-based adaptive ROM framework updates reduced bases with occasional full-order snapshots, showing improved accuracy and efficiency over direct adaptation baselines on Burgers, Sod, and rotating detonation engine problems.
-
Two-Parameter Flows for Learning Population Dynamics of Physical Systems
Two-parameter flows learn base-to-marginal transports via conditional flow matching then extract unique physics-time velocities by regression on synthetic trajectories, inheriting regularity and scaling to high dimensions while permitting non-gradient dynamics.
-
When can a neural operator replace a coarse solve? Architectural principles for two-level preconditioning
The Neural Green's Operator matches exact coarse-solve iteration counts in two-level preconditioners for diffusion and advection-diffusion problems when inputs are integrated against the output basis.
-
Pattern-based tests for two-dimensional copulas
A functional central limit theorem for pattern frequencies in 2D samples enables nonparametric goodness-of-fit, two-sample, and symmetry tests for copulas, with bootstrap critical values and parametric examples.
-
A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
A 4.509-approximation algorithm for generalized min-sum set cover that improves the prior 4.642 bound via refined LP analysis and new lower-tail bounds on sums of independent Bernoullis.
-
FalconGEMM: Surpassing Hardware Peaks with Lower-Complexity Matrix Multiplication
FalconGEMM delivers a framework with deployment, group-parallel execution, and analytical decision modules that makes lower-complexity matrix multiplication practical, beating cuBLAS and similar libraries by 7.59-17.85% on LLM tasks.
-
MAEO: Multiobjective Animorphic Ensemble Optimization for Scalable Large-scale Engineering Applications
MAEO is a new ensemble framework that runs NSGA-III, CTAEA, AGEMOEA2 and SPEA2 in parallel islands with parameter-free hypervolume assessment and strict Pareto-rank selection, showing competitive or better results on DTLZ/ZDT benchmarks and identifying improved nuclear reactor designs.
-
Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS
Restricted Syndrome Decoding reduces to Regular Syndrome Decoding and Closest Vector Problem via structured low-norm vectors in constructed codes, broadening attacks on the CROSS signature scheme.
-
Lipschitz bounds for integral kernels
Explicit Lipschitz constants and continuity conditions are derived for feature maps of integral kernels, with closed-form results for Gaussian, ReLU neural network, and Matérn kernels under moment conditions.
-
An Efficient Batch Solver for the Singular Value Decomposition on GPUs
A new GPU-oriented batch SVD solver based on the one-sided Jacobi method delivers significant speedups over vendor libraries and prior open-source implementations across precisions and matrix shapes.
-
Technical results on the convergence of quasi-Newton methods for nonsmooth optimization
Sufficient conditions on eigenvalue vanishing in quasi-Newton updates, observed numerically, are shown to imply convergence to criticality for piecewise differentiable nonsmooth functions, along with the method's ability to explore piecewise structure.
-
Mixed-precision iterative refinement for low-rank Lyapunov equations
Develops mixed-precision iterative refinement for low-rank Lyapunov equations with rounding error analysis enabling reduced precision for moderately conditioned problems.
-
Dimension and model reduction approaches for linear Bayesian inverse problems with rank-deficient prior covariances
New dimension and model reduction techniques for linear Bayesian inverse problems with rank-deficient priors, with approximation guarantees and efficiency demonstrations for high-dimensional inference.
-
The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
New analysis framework yields single-machine deterministic competitive ratio of 2.316513 and randomized 2.152271, plus multi-machine bounds of 2.77629-(0.45977/m) deterministic and 2.51098-(0.3587/m) randomized.
-
Geometric Crossing-Minimization -- A Scalable Randomized Approach
Presents a scalable randomized algorithm for geometric crossing minimization, including a theoretical approximation guarantee for vertex repositioning and experimental results on graphs with up to 13,000 edges.
-
CHESS: CHEbyshev pSeudo-Spectral transport for Feynman integral differential equations
CHESS package implements Chebyshev-Lobatto spectral collocation for transporting epsilon-factorized differential equations of Feynman master integrals with benchmarks showing rapid convergence and shorter wall times than local series methods.
-
Enforcing Trust Accountability with Backward Propagation
RepuLink couples endorsement and interaction networks with backward penalty/reward propagation to enforce endorser accountability and provide weighted trust initialization for new nodes.
-
Optimal Spectral Design with Prior Information
Convex reformulation and polynomial-time algorithm for spectral design problems that update a prior information matrix by rank-one updates under Euclidean-norm bounds on the design vectors.
-
Early Pruning for Public Transport Routing
Pre-sorting transfers by duration and pruning non-improving ones cuts RAPTOR-family query times by up to 57% while preserving optimality.