BriefGPT.xyz
May, 2017
k-SUM和相关问题的近似最优线性决策树
Near-optimal linear decision trees for k-SUM and related problems
HTML
PDF
Daniel M. Kane, Shachar Lovett, Shay Moran
TL;DR
本文研究了求解离散几何和组合问题中的线性决策树,提出了一种基于推理维度的新方法来构造线性决策树,并通过比较查询来解决$K$-SUM问题、排序sumsets $A+B$以及解决子集-SUM问题,与统计学习和离散几何的研究有着密切联系。
Abstract
We construct near optimal
linear decision trees
for a variety of decision problems in
combinatorics
and
discrete geometry
. For example, fo
→