APSP的后果、三角探测和3SUM硬性区分确定论和非确定论 (Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism) - 专知论文

会员服务 ·

0

分离的 · 值域 · Oracle · 类别 ·

2020 年 11 月 26 日

Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism

翻译：APSP的后果、三角探测和3SUM硬性区分确定论和非确定论

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

相关内容

分离的

Fariz Darari简明《博弈论Game Theory》介绍，35页ppt

Fariz Darari简明《博弈论Game Theory》介绍，35页ppt

专知会员服务

109+阅读 · 2020年5月15日

【Facebook AI】低资源机器翻译，74页ppt

【Facebook AI】低资源机器翻译，74页ppt

专知会员服务

29+阅读 · 2020年4月8日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

94+阅读 · 2020年3月12日

可视化特征属性基线的影响，Visualizing the Impact of Feature Attribution Baselines

可视化特征属性基线的影响，Visualizing the Impact of Feature Attribution Baselines

专知会员服务

9+阅读 · 2020年1月16日

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

专知会员服务

34+阅读 · 2019年10月17日

Stabilizing Transformers for Reinforcement Learning

Stabilizing Transformers for Reinforcement Learning

专知会员服务

58+阅读 · 2019年10月17日

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

专知会员服务

56+阅读 · 2019年10月17日

强化学习最新教程，17页pdf

强化学习最新教程，17页pdf

专知会员服务

174+阅读 · 2019年10月11日

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

专知会员服务

81+阅读 · 2019年10月9日

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

专知会员服务

39+阅读 · 2019年10月9日

Transferring Knowledge across Learning Processes

Transferring Knowledge across Learning Processes

CreateAMind

27+阅读 · 2019年5月18日

A Technical Overview of AI & ML in 2018 & Trends for 2019

A Technical Overview of AI & ML in 2018 & Trends for 2019

待字闺中

16+阅读 · 2018年12月24日

CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习

CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习

Call4Papers

5+阅读 · 2018年12月7日

【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree

【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree

专知

6+阅读 · 2017年12月11日

【论文】变分推断（Variational inference)的总结

【论文】变分推断（Variational inference)的总结

机器学习研究会

39+阅读 · 2017年11月16日

关关的刷题日记13——Leetcode 414. Third Maximum Number

关关的刷题日记13——Leetcode 414. Third Maximum Number

专知

3+阅读 · 2017年10月8日

【学习】Hierarchical Softmax

【学习】Hierarchical Softmax

机器学习研究会

4+阅读 · 2017年8月6日

Auto-Encoding GAN

Auto-Encoding GAN

CreateAMind

7+阅读 · 2017年8月4日

强化学习族谱

强化学习族谱

CreateAMind

26+阅读 · 2017年8月2日

强化学习 cartpole_a3c

强化学习 cartpole_a3c

CreateAMind

9+阅读 · 2017年7月21日

Scalable Distributed Approximation of Internal Measures for Clustering Evaluation

Arxiv

0+阅读 · 2021年1月20日

Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing

Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing

Arxiv

0+阅读 · 2021年1月19日

Telescopers for differential forms with one parameter

Arxiv

0+阅读 · 2021年1月19日

Obstructions for bounded shrub-depth and rank-depth

Arxiv

0+阅读 · 2021年1月18日

A simple geometric proof for the benefit of depth in ReLU networks

Arxiv

0+阅读 · 2021年1月18日

Optimal Pre-Processing to Achieve Fairness and Its Relationship with Total Variation Barycenter

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日

Products of Euclidean metrics and applications to proximity questions among curves

Arxiv

3+阅读 · 2020年4月13日

DeepFakes: a New Threat to Face Recognition? Assessment and Detection

Arxiv

6+阅读 · 2018年12月20日

VIP会员

文章信息

相关主题

相关VIP内容

Fariz Darari简明《博弈论Game Theory》介绍，35页ppt

Fariz Darari简明《博弈论Game Theory》介绍，35页ppt

专知会员服务

109+阅读 · 2020年5月15日

【Facebook AI】低资源机器翻译，74页ppt

【Facebook AI】低资源机器翻译，74页ppt

专知会员服务

29+阅读 · 2020年4月8日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

94+阅读 · 2020年3月12日

可视化特征属性基线的影响，Visualizing the Impact of Feature Attribution Baselines

可视化特征属性基线的影响，Visualizing the Impact of Feature Attribution Baselines

专知会员服务

9+阅读 · 2020年1月16日

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

专知会员服务

34+阅读 · 2019年10月17日

Stabilizing Transformers for Reinforcement Learning

Stabilizing Transformers for Reinforcement Learning

专知会员服务

58+阅读 · 2019年10月17日

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

专知会员服务

56+阅读 · 2019年10月17日

强化学习最新教程，17页pdf

强化学习最新教程，17页pdf

专知会员服务

174+阅读 · 2019年10月11日

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

专知会员服务

81+阅读 · 2019年10月9日

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

专知会员服务

39+阅读 · 2019年10月9日

热门VIP内容

相关资讯

Transferring Knowledge across Learning Processes

Transferring Knowledge across Learning Processes

CreateAMind

27+阅读 · 2019年5月18日

A Technical Overview of AI & ML in 2018 & Trends for 2019

A Technical Overview of AI & ML in 2018 & Trends for 2019

待字闺中

16+阅读 · 2018年12月24日

CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习

CCF C类 | IJCNN 2019 Special Section : 信息论与深度学习

Call4Papers

5+阅读 · 2018年12月7日

【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree

【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree

专知

6+阅读 · 2017年12月11日

【论文】变分推断（Variational inference)的总结

【论文】变分推断（Variational inference)的总结

机器学习研究会

39+阅读 · 2017年11月16日

关关的刷题日记13——Leetcode 414. Third Maximum Number

关关的刷题日记13——Leetcode 414. Third Maximum Number

专知

3+阅读 · 2017年10月8日

【学习】Hierarchical Softmax

【学习】Hierarchical Softmax

机器学习研究会

4+阅读 · 2017年8月6日

Auto-Encoding GAN

Auto-Encoding GAN

CreateAMind

7+阅读 · 2017年8月4日

强化学习族谱

强化学习族谱

CreateAMind

26+阅读 · 2017年8月2日

强化学习 cartpole_a3c

强化学习 cartpole_a3c

CreateAMind

9+阅读 · 2017年7月21日

相关论文

Scalable Distributed Approximation of Internal Measures for Clustering Evaluation

Arxiv

0+阅读 · 2021年1月20日

Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing

Exchangeable Bernoulli distributions: high dimensional simulation, estimate and testing

Arxiv

0+阅读 · 2021年1月19日

Telescopers for differential forms with one parameter

Arxiv

0+阅读 · 2021年1月19日

Obstructions for bounded shrub-depth and rank-depth

Arxiv

0+阅读 · 2021年1月18日

A simple geometric proof for the benefit of depth in ReLU networks

Arxiv

0+阅读 · 2021年1月18日

Optimal Pre-Processing to Achieve Fairness and Its Relationship with Total Variation Barycenter

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日

Products of Euclidean metrics and applications to proximity questions among curves

Arxiv

3+阅读 · 2020年4月13日

DeepFakes: a New Threat to Face Recognition? Assessment and Detection

Arxiv

6+阅读 · 2018年12月20日

微信扫码咨询专知VIP会员