会员服务
分离的 · 值域 · Oracle · 类别 ·
2020 年 11 月 26 日
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
翻译：APSP的后果、三角探测和3SUM硬性区分确定论和非确定论
Andrzej Lingas
Andrzej Lingas
from arxiv, The section on range reduction in the previous version contained a flaw in a proof and therefore it has been removed

We present implications from the known conjectures like APSP, 3SUM and ETH in a form of a negated containment of a linear-time with a non-deterministic logarithmic-bit oracle in a respective deterministic bounded-time class They are different for different conjectures and they exhibit in particular the dependency on the input range parameters.


翻译：我们提出了已知的预测,如APSP、3SUM和ETH, 其影响形式是,将线性时间与非确定性对数比标符一道,在不同的确定性约束性时间等级中以否定的方式封闭起来。 不同的预测不同,它们特别显示出对输入范围参数的依赖性。
0
下载
关闭预览

相关内容

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
96+阅读 · 2020年3月12日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
182+阅读 · 2019年10月11日
【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性
【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性
专知会员服务
83+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
专知
6+阅读 · 2017年12月11日
关关的刷题日记13——Leetcode 414. Third Maximum Number
关关的刷题日记13——Leetcode 414. Third Maximum Number
专知
3+阅读 · 2017年10月8日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing
Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing
Arxiv
0+阅读 · 2021年1月19日
A simple geometric proof for the benefit of depth in ReLU networks
Arxiv
0+阅读 · 2021年1月18日
APX-Hardness and Approximation for the k-Burning Number Problem
Arxiv
0+阅读 · 2021年1月17日
Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
Arxiv
0+阅读 · 2021年1月14日
DeepFakes: a New Threat to Face Recognition? Assessment and Detection
Arxiv
6+阅读 · 2018年12月20日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
分离的
值域
Oracle
类别
相关VIP内容
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
96+阅读 · 2020年3月12日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
182+阅读 · 2019年10月11日
【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性
【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性
专知会员服务
83+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
热门VIP内容
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
专知
6+阅读 · 2017年12月11日
关关的刷题日记13——Leetcode 414. Third Maximum Number
关关的刷题日记13——Leetcode 414. Third Maximum Number
专知
3+阅读 · 2017年10月8日
强化学习族谱
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing
Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing
Arxiv
0+阅读 · 2021年1月19日
A simple geometric proof for the benefit of depth in ReLU networks
Arxiv
0+阅读 · 2021年1月18日
APX-Hardness and Approximation for the k-Burning Number Problem
Arxiv
0+阅读 · 2021年1月17日
Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
Arxiv
0+阅读 · 2021年1月14日
DeepFakes: a New Threat to Face Recognition? Assessment and Detection
Arxiv
6+阅读 · 2018年12月20日
Top
微信扫码咨询专知VIP会员
Top