首页>外文期刊>Theory of Computing

Theory of Computing

SCIEI

中文名称：计算理论

ISSN：1557-2862
出版周期：-

发文量：176

期刊论文

热门论文

年度选择

2021
- 第si期
2020
- 第1期
2019
- 第nullaspeca期
2018
- 第nullaspeca期
2017
- 第2期
- 第18期
2016
- 第2期
2015
- 第2期
2014
- 第2期
- 第6期
2013
- 第6期
2012
- 第2期
- 第6期
2011
- 第2期
2010
- 第2期

更多>>

全选（0）

1.Distance Transforms of Sampled Functions

机译：采样函数的距离变换
- 作者：Pedro F. Felzenszwalb;Daniel P. Huttenlocher
- 期刊名称：《Theory of Computing》 | 2012年第6期
2.Revenue Submodularity

机译：收入亚模块
- 作者：Shaddin Dughmi;Tim Roughgarden;Mukund Sundararajan
- 期刊名称：《Theory of Computing》 | 2012年第6期
3.Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions

机译：几乎$ k $ -Wise与$ k $ -Wise独立的排列以及统一的常规集体操作
- 作者：Noga Alon;Shachar Lovett
- 期刊名称：《Theory of Computing》 | 2013年第6期
4.Optimal Hitting Sets for Combinatorial Shapes

机译：组合形状的最佳击球集
- 作者：Aditya Bhaskara;Devendra Desai;Srikanth Srinivasan
- 期刊名称：《Theory of Computing》 | 2013年第6期
5.Constructing Small-Bias Sets from Algebraic-Geometric Codes

机译：从代数几何代码构造小偏差集合
- 作者：Avraham Ben-Aroya;Amnon Ta-Shma
- 期刊名称：《Theory of Computing》 | 2013年第6期
6.Improved Inapproximability Results for Maximum $k$-Colorable Subgraph

机译：改进了最大$ k $可着色子图的不可逼近结果
- 作者：Venkatesan Guruswami;Ali Kemal Sinop
- 期刊名称：《Theory of Computing》 | 2013年第6期
7.Hardness of Vertex Deletion and Project Scheduling

机译：顶点删除的难度和项目调度
- 作者：Ola Svensson
- 期刊名称：《Theory of Computing》 | 2013年第6期
8.Hamming Approximation of NP Witnesses

机译：NP证人的汉明近似
- 作者：Daniel Sheldon;Neal E. Young
- 期刊名称：《Theory of Computing》 | 2013年第6期
9.The Complexity of the Fermionant and Immanants of Constant Width

机译：等宽宽度的费米子和内man子的复杂性
- 作者：Stephan Mertens;Cristopher Moore
- 期刊名称：《Theory of Computing》 | 2013年第6期
10.Guest Editors’ Foreword

机译：客座编辑的前言
- 作者：Elchanan Mossel;Ryan O’Donnell
- 期刊名称：《Theory of Computing》 | 2013年第6期
11.A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta

机译：低深度决策树给出的单调函数，它不是近似Junta
- 作者：Daniel Kane
- 期刊名称：《Theory of Computing》 | 2013年第6期
12.Testing Properties of Collections of Distributions

机译：测试分布集合的属性
- 作者：Reut Levi;Dana Ron;Ronitt Rubinfeld
- 期刊名称：《Theory of Computing》 | 2013年第6期
13.A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes

机译：测试广义Reed-Muller码查询复杂度的新上限
- 作者：Noga Ron-Zewi;Madhu Sudan
- 期刊名称：《Theory of Computing》 | 2013年第6期
14.Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

机译：绕$ d $至$ 1 $满足严格包含至少四个宽度奇偶性的可满足谓词的近似抗性
- 作者：Cenny Wenner
- 期刊名称：《Theory of Computing》 | 2013年第6期
15.The Computational Complexity of Linear Optics

机译：线性光学的计算复杂性
- 作者：Scott Aaronson;Alex Arkhipov
- 期刊名称：《Theory of Computing》 | 2013年第6期
16.Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream

机译：简单哈希函数为何起作用：利用数据流中的熵
- 作者：Kai-Min Chung;Michael Mitzenmacher;Salil Vadhan
- 期刊名称：《Theory of Computing》 | 2013年第6期
17.On Beating the Hybrid Argument

机译：关于击败混合论点
- 作者：Bill Fefferman;Ronen Shaltiel;Christopher Umans;Emanuele Viola
- 期刊名称：《Theory of Computing》 | 2013年第6期
18.A Two-Prover One-Round Game with Strong Soundness

机译：稳健的两回合一回合比赛
- 作者：Subhash Khot;Muli Safra
- 期刊名称：《Theory of Computing》 | 2013年第6期
19.Approximating the AND-OR Tree

机译：逼近AND-OR树
- 作者：Alexander A. Sherstov
- 期刊名称：《Theory of Computing》 | 2013年第6期
20.Making Polynomials Robust to Noise

机译：使多项式对噪声稳健
- 作者：Alexander A. Sherstov
- 期刊名称：《Theory of Computing》 | 2013年第6期
21.Quantum Money from Hidden Subspaces

机译：隐藏子空间的量子货币
- 作者：Scott Aaronson;Paul Christiano
- 期刊名称：《Theory of Computing》 | 2013年第6期
22.Guest Editors’ Foreword

机译：客座编辑的前言
- 作者：Alexandr Andoni;Atri Rudra
- 期刊名称：《Theory of Computing》 | 2013年第6期
23.On the Real $au$-Conjecture and the Distribution of Complex Roots

机译：关于实数$ tau $猜想和复数根的分布
- 作者：Pavel Hrube?
- 期刊名称：《Theory of Computing》 | 2013年第6期
24.Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

机译：某些满意问题的消息传递算法的完全收敛
- 作者：Uriel Feige;Elchanan Mossel;Dan Vilenchik
- 期刊名称：《Theory of Computing》 | 2013年第6期
25.The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems

机译：平移不变平铺和哈密顿问题的量子和古典复杂性
- 作者：Daniel Gottesman;Sandy Irani
- 期刊名称：《Theory of Computing》 | 2013年第6期
26.Inapproximability of NP-Complete Variants of Nash Equilibrium

机译：Nash平衡的NP完全变体的不可逼近
- 作者：Per Austrin;Mark Braverman;Eden Chlamtá?
- 期刊名称：《Theory of Computing》 | 2013年第6期
27.Hypercontractivity Via the Entropy Method

机译：通过熵方法的超收缩
- 作者：Eric Blais;Li-Yang Tan
- 期刊名称：《Theory of Computing》 | 2013年第6期
28.Pseudorandomness for Width-2 Branching Programs

机译：Width-2分支程序的伪随机性
- 作者：Andrej Bogdanov;Zeev Dvir;Elad Verbin;Amir Yehudayoff
- 期刊名称：《Theory of Computing》 | 2013年第6期
29.Towards an Optimal Separation of Space and Length in Resolution

机译：寻求分辨率上空间和长度的最佳分离
- 作者：Jakob Nordstr?m;Johan H?stad
- 期刊名称：《Theory of Computing》 | 2013年第6期
30.Satisfying Degree-$d$ Equations over $GF[2]^n$

机译：满足$ GF [2] ^ n $的度-$ d $方程
- 作者：Johan H?stad
- 期刊名称：《Theory of Computing》 | 2013年第6期
31.The Power of Nondeterminism in Self-Assembly

机译：自我组装中不确定性的力量
- 作者：Nathaniel Bryans;Ehsan Chiniforooshan;David Doty;Lila Kari;Shinnosuke Seki
- 期刊名称：《Theory of Computing》 | 2013年第6期
32.Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic

机译：常数级和小特征场上的多项式源提取器
- 作者：Eli Ben-Sasson;Ariel Gabizon
- 期刊名称：《Theory of Computing》 | 2013年第6期
33.Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube

机译：超立方体中球形均值的无量纲$ L_2 $极大不等式
- 作者：Aram W. Harrow;Alexandra Kolla;Leonard J. Schulman
- 期刊名称：《Theory of Computing》 | 2014年第6期
34.Grothendieck Inequalities for Semidefinite Programs with Rank Constraint

机译：具有秩约束的半定程序的Grothendieck不等式
- 作者：Jop Bri?t;Fernando Mário de Oliveira Filho;Frank Vallentin
- 期刊名称：《Theory of Computing》 | 2014年第6期
35.Lower Bounds for the Average and Smoothed Number of Pareto-Optima

机译：帕累托最优的平均数和平滑数的下界
- 作者：Tobias Brunsch;Navin Goyal;Luis Rademacher;Heiko R?glin
- 期刊名称：《Theory of Computing》 | 2014年第6期
36.Width-Parametrized SAT: Time--Space Tradeoffs

机译：宽度参数化SAT：时空折衷
- 作者：Eric Allender;Shiteng Chen;Tiancheng Lou;Periklis A. Papakonstantinou;Bangsheng Tang
- 期刊名称：《Theory of Computing》 | 2014年第6期
37.Efficient Rounding for the Noncommutative Grothendieck Inequality

机译：非可交换格洛腾迪克不等式的有效舍入
- 作者：Assaf Naor;Oded Regev;Thomas Vidick
- 期刊名称：《Theory of Computing》 | 2014年第6期
38.Bounding the Sensitivity of Polynomial Threshold Functions

机译：限制多项式阈值函数的灵敏度
- 作者：Prahladh Harsha;Adam Klivans;Raghu Meka
- 期刊名称：《Theory of Computing》 | 2014年第6期
39.An Optimal Lower Bound for Monotonicity Testing over Hypergrids

机译：超网格上单调性测试的最优下界
- 作者：Deeparnab Chakrabarty;C. Seshadhri
- 期刊名称：《Theory of Computing》 | 2014年第6期
40.Tight Bounds for Monotone Switching Networks via Fourier Analysis

机译：通过傅立叶分析确定单调交换网络的严格边界
- 作者：Siu Man Chan;Aaron Potechin
- 期刊名称：《Theory of Computing》 | 2014年第6期
41.On Reconstruction and Testing of Read-Once Formulas

机译：一次公式的重构与检验
- 作者：Amir Shpilka;Ilya Volkovich
- 期刊名称：《Theory of Computing》 | 2014年第6期
42.Matchgates Revisited

机译：重温火柴门
- 作者：Jin-Yi Cai;Aaron Gorenstein
- 期刊名称：《Theory of Computing》 | 2014年第6期
43.Query Complexity Lower Bounds for Reconstruction of Codes

机译：查询复杂度下界以重构代码
- 作者：Sourav Chakraborty;Eldar Fischer;Arie Matsliah
- 期刊名称：《Theory of Computing》 | 2014年第6期
44.Approximation Resistance on Satisfiable Instances for Sparse Predicates

机译：稀疏谓词在可满足实例上的近似抗性
- 作者：Sangxia Huang
- 期刊名称：《Theory of Computing》 | 2014年第6期
45.The Need for Structure in Quantum Speedups

机译：量子加速中对结构的需求
- 作者：Scott Aaronson;Andris Ambainis
- 期刊名称：《Theory of Computing》 | 2014年第6期
46.Competing-Provers Protocols for Circuit Evaluation

机译：电路评估的竞争证明协议
- 作者：Gillat Kol;Ran Raz
- 期刊名称：《Theory of Computing》 | 2014年第6期
47.Improved Inapproximability for TSP

机译：改善了TSP的不可逼近性
- 作者：Michael Lampis
- 期刊名称：《Theory of Computing》 | 2014年第6期
48.Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

机译：有时间限制的辅助下推自动机的对称性与不确定性同时发生
- 作者：Eric Allender;Klaus-J?rn Lange
- 期刊名称：《Theory of Computing》 | 2014年第6期
49.Learning $k$-Modal Distributions via Testing

机译：通过测试学习$ k $-模态分布
- 作者：Constantinos Daskalakis;Ilias Diakonikolas;Rocco A. Servedio
- 期刊名称：《Theory of Computing》 | 2014年第6期
50.How Many Bits Can a Flock of Birds Compute?

机译：一群鸟可以计算多少位？
- 作者：Bernard Chazelle
- 期刊名称：《Theory of Computing》 | 2014年第6期
51.Decoding Reed–Muller Codes over Product Sets

机译：解码产品集上的里德-穆勒码
- 作者：John Y. Kim;Swastik Kopparty
- 期刊名称：《Theory of Computing》 | 2017年第18期
52.Arithmetic Circuits with Locally Low Algebraic Rank

机译：具有局部低代数等级的算术电路
- 作者：Mrinal Kumar;Shubhangi Saraf
- 期刊名称：《Theory of Computing》 | 2017年第18期
53.Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals

机译：超实数下界，用于在实数上查询本地可查询代码的3个查询
- 作者：Zeev Dvir;Shubhangi Saraf;Avi Wigderson
- 期刊名称：《Theory of Computing》 | 2017年第18期
54.Tight Hardness of the Non-Commutative Grothendieck Problem

机译：非交换Grothendieck问题的紧性
- 作者：Jop Bri?t;Oded Regev;Rishi Saket
- 期刊名称：《Theory of Computing》 | 2017年第18期
55.Guest Editor’s Foreword

机译：客座编辑的前言
- 作者：Prahladh Harsha
- 期刊名称：《Theory of Computing》 | 2017年第18期
56.On the Hardness of Approximating Balanced Homogenous 3-Lin

机译：关于平衡均质3-Lin的硬度
- 作者：Johan H?stad;Rajsekar Manokaran
- 期刊名称：《Theory of Computing》 | 2017年第18期
57.Towards a Characterization of Approximation Resistance for Symmetric CSPs

机译：寻求对称CSP的近似电阻特性
- 作者：Venkatesan Guruswami;Euiwoong Lee
- 期刊名称：《Theory of Computing》 | 2017年第18期
58.Monotone Projection Lower Bounds from Extended Formulation Lower Bounds

机译：扩展配方下界的单调投影下界
- 作者：Joshua A. Grochow
- 期刊名称：《Theory of Computing》 | 2017年第18期
59.A Constructive Lovász Local Lemma for Permutations

机译：置换的建设性马局部引理
- 作者：David G. Harris;Aravind Srinivasan
- 期刊名称：《Theory of Computing》 | 2017年第18期
60.Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

机译：恒定宽度和任意顺序，一次过的遗忘算术分支程序的身份测试
- 作者：Rohit Gurjar;Arpita Korwar;Nitin Saxena
- 期刊名称：《Theory of Computing》 | 2017年第18期
61.Improved NP-Inapproximability for $2$-Variable Linear Equations

机译：改进的$ 2 $线性方程组的NP不逼近度
- 作者：Johan H?stad;Sangxia Huang;Rajsekar Manokaran;Ryan ODonnell;John Wright
- 期刊名称：《Theory of Computing》 | 2017年第18期
62.A Randomized Online Quantile Summary in $O((1/arepsilon) log(1/arepsilon))$ Words

机译：$ O（（1 / varepsilon） log（1 / varepsilon））$字中的随机在线分位数摘要
- 作者：David Felber;Rafail Ostrovsky
- 期刊名称：《Theory of Computing》 | 2017年第18期
63.The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials

机译：基本对称多项式的转移偏导数复杂度
- 作者：Hervé Fournier;Nutan Limaye;Meena Mahajan;Srikanth Srinivasan
- 期刊名称：《Theory of Computing》 | 2017年第18期
64.From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems

机译：从所有约束满足问题的弱到强线性规划缺口
- 作者：Mrinalkanti Ghosh;Madhur Tulsiani
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
65.Randomized Query Complexity of Sabotaged and Composed Functions

机译：破坏和组合函数的随机查询复杂度
- 作者：Shalev Ben-David;Robin Kothari
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
66.Guest Editors’ Foreword

机译：客座编辑的前言
- 作者：Shachar Lovett;Ryan O’Donnell
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
67.The Complexity of Computing the Optimal Composition of Differential Privacy

机译：计算差异隐私最佳组成的复杂性
- 作者：Jack Murtagh;Salil Vadhan
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
68.Trading Information Complexity for Error

机译：交易信息错综复杂
- 作者：Yuval Dagan;Yuval Filmus;Hamed Hatami;Yaqiao Li
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
69.A Deterministic PTAS for the Commutative Rank of Matrix Spaces

机译：矩阵空间可交换秩的确定性PTAS
- 作者：Markus Bl?ser;Gorav Jindal;Anurag Pandey
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
70.Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels

机译：无记忆二进制输入输出对称通道的显式无速率代码
- 作者：Benny Applebaum;Liron David;Guy Even
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
71.Linear-Time Algorithm for Quantum 2SAT

机译：量子2SAT的线性时间算法
- 作者：Itai Arad;Miklos Santha;Aarthi Sundaram;Shengyu Zhang
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
72.Quantum Homomorphic Encryption for Polynomial-Size Circuits

机译：多项式大小电路的量子同态加密
- 作者：Yfke Dulek;Christian Schaffner;Florian Speelman
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
73.Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

机译：小型阈值电路的平均情况下界和可满足性算法
- 作者：Ruiwen Chen;Rahul Santhanam;Srikanth Srinivasan
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
74.How to Verify a Quantum Computation

机译：如何验证量子计算
- 作者：Anne Broadbent
- 期刊名称：《Theory of Computing》 | 2018年第nullaspeca期
75.Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions

机译：测试$ k $-单调性：布尔函数的兴衰
- 作者：Clément L. Canonne;Elena Grigorescu;Siyao Guo;Akash Kumar;Karl Wimmer
- 期刊名称：《Theory of Computing》 | 2019年第nullaspeca期
- property testingboolean functionsmonotonicitylearning;
76.Distributed Corruption Detection in Networks

机译：网络中的分布式损坏检测
- 作者：Noga Alon;Elchanan Mossel;Robin Pemantle
- 期刊名称：《Theory of Computing》 | 2020年第1期
- distributed computingexpander graphsPMC modelgraph separatorsnetwork testing;
77.Limits on the Universal Method for Matrix Multiplication
- 作者：Alman Josh
- 期刊名称：《theory of computing》 | 2021年第si期
- matrix multiplication;
- algebraic complexity;
- COMPLEXITY;
78.The Large-Error Approximate Degree of AC(0)
- 作者：Bun Mark;Thaler Justin
- 期刊名称：《theory of computing》 | 2021年第si期
79.Hardness Magnification Near State-of-the-Art Lower Bounds
- 作者：Oliveira Igor C.;Pich Jan;Santhanam Rahul
- 期刊名称：《theory of computing》 | 2021年第si期
- circuit complexity;
- minimum circuit size problem;
- Kolmogorov complexity;
- CIRCUIT LOWER BOUNDS;
- PSEUDORANDOM GENERATORS;
- SIZE;
- COMPLEXITY;
- TIME;
80.Proof Complexity Lower Bounds from Algebraic Circuit Complexity
- 作者：Forbes Michael A.;Shpilka Amir;Tzameret IddoWigderson Avi
- 期刊名称：《theory of computing》 | 2021年第si期
81.Barriers for Fast Matrix Multiplication from Irreversibility
- 作者：Christandl Matthias;Vrana Peter;Zuiddam Jeroen
- 期刊名称：《theory of computing》 | 2021年第si期
- algebraic complexity;
- matrix multiplication;
- barriers;
- tensors;
- tensor rank;
- COMPLEXITY;

客服邮箱：kefu@zhangqiaokeyan.com

客服微信
服务号