We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous graphs including the random graph, and for expansions of the order of the rationals. Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize those CSPs which are solvable by local consistency methods, again using the same machinery.


翻译:我们开发了光滑近似值的新机制, 并运用它来确认CSP的二分法猜想, 用于随机比赛的一阶降序、 各种同质图表, 包括随机图表, 以及理性顺序的扩展。 除了获得这些二分法结果外, 我们还展示了我们的新验证技术如何允许统一和大大简化文献的先前结果。 除了最后的结构外, 我们还用同样的机器来描述那些可以由本地一致性方法解决的CSP。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【机器学习术语宝典】机器学习中英文术语表
专知会员服务
59+阅读 · 2020年7月12日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
39+阅读 · 2019年10月9日
已删除
将门创投
5+阅读 · 2020年3月2日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2021年3月7日
Arxiv
0+阅读 · 2021年3月6日
Function Approximation via Sparse Random Features
Arxiv
0+阅读 · 2021年3月4日
VIP会员
相关资讯
已删除
将门创投
5+阅读 · 2020年3月2日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员