首页>外文期刊>其他>ACM Transactions on Computational Theory

ACM Transactions on Computational Theory

中文名称：ACM计算理论交易

ISSN：1942-3454
出版周期：

发文量：155

期刊论文

热门论文

年度选择

更多>>

全选（0）

1.On Hardness of Multilinearization and VNP-Completeness in Characteristic 2

机译：特征2中的多重线性化的难度和VNP的完全性
- 作者：P. HRUBES
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第1期
2.Noncommutative Valiant's Classes: Structure and Complete Problems

机译：非交换Valiant的类：结构和完全问题
- 作者：V. ARVIND;P. S. JOGLEKAR;S. RAJA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第1期
3.Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method

机译：不确定性和涅西普鲁克下界方法的抽象表示
- 作者：PAUL BEAME;NATHAN GROSSHANS;PIERRE MCKENZIE;LUC SEGOUFIN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第1期
- Branching programs;
- binary formulas;
- limited nondeterminism;
4.Small Depth Proof Systems

机译：小深度验证系统
- 作者：ANDREAS KREBS;NUTAN LIMAYE;MEENA MAHAJAN;KARTEEK SREENIVASAIAH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第1期
5.Relative Discrepancy Does Not Separate Information and Communication Complexity

机译：相对差异不能消除信息和通信的复杂性
- 作者：LI LA FONTES;RAHUL JAIN;IORDANIS KERENIDIS;SOPHIE LAPLANTE;MATHIEU LAURIERE;JEREMIE ROLAND
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第1期
- Communication complexity;
- information complexity;
- relative discrepancy;
- partition;
6.Min/Max-Poly Weighting Schemes and the NL versus UL Problem

机译：最小/最大多边形加权方案以及NL与UL问题
- 作者：ANANT DHAYAL JAYALAL SARMA;SAURABH SAWLANI
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第2期
- Unambiguous logspace;
- graph reachability problem;
- weighting schemes;
7.Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

机译：用于非布尔多尺寸电路的具有最佳种子长度的伪随机发生器
- 作者：SERGEI ARTEMENKO;RONEN SHALTIEL
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第2期
- Pseudorandomness;
- pseudorandom generators;
- hardness versus ran domness;
- randomness complexity of sampling;
8.Exact Perfect Matching in Complete Graphs

机译：完整图形中的精确完美匹配
- 作者：ROHIT GURJAR;ARPITA KORWAR;JOCHEN MESSNER;THOMAS THIERAUF
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第2期
- Perfect matching;
- exact perfect matching;
- complete graphs;
- computa-tional complexity;
9.A Complexity Trichotomy for Approximately CountingList H-Colorings

机译：近似计算列表H色的复杂性三分法
- 作者：ANDREAS GALANIS;LESLIE ANN GOLDBERG;MARK JERRUM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第2期
- Approximate counting;
- graph homomorphisms;
- list colorings;
10.Lower Bounds for Constant Query ffine-lnvariant LCCs and LTCs

机译：恒定查询有限不变LCC和LTC的下界
- 作者：ARNAB BHATTACHARYYA;SIVAKANTH GOPI
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第2期
- Locally correctable code;
- locally testable code;
- affine invariance;
- Gowers uniformity norm;
11.Asking the Metaquestions in Constraint Tractability

机译：询问约束可牵引性的元问题
- 作者：HUBIE CHEN;BENOIT LAROSE
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第3期
- Constraint satisfaction;
- tractability;
- metaquestions;
- polymorphisms;
- homomorphisms;
12.Hardness of Approximation for Strip Packing

机译：带状包装的近似硬度
- 作者：ANNA ADAMASZEK;TOMASZ KOCIUMAKA;MARCIN PILIPCZUK;MICHAŁ PILIPCZUK
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第3期
- Strip packing;
- packing problems;
- approximation hardness;
13.Finding Consensus Strings with Small Length Difference between Input and Solution Strings

机译：查找输入字符串和解决方案字符串之间的长度差异很小的共识字符串
- 作者：MARKUSL. SCHMID
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第3期
- Parameterised complexity;
- multivariate algorithmics;
- hard string problems;
14.Canonizing Graphs of Bounded Tree Width in Logspace

机译：对数空间中有界树宽的规范化图
- 作者：MICHAEL ELBERFELD;PASCAL SCHWEITZER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第3期
- Algorithmic graph theory;
- computational complexity;
- graph canonization;
- graph isomorphism;
- logspace algorithms;
- free width;
15.Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

机译：证明复杂度的模多项式层次结构：将交替理解为硬度的来源
- 作者：HUBIE CHEN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2017年第3期
- Proof complexity;
- quantified formulas;
- polynomial hierarchy;
16.Characterizing Arithmetic Read-Once Formulae

机译：表征算术一次公式
- 作者：ILYA VOLKOVICH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第1期
- Arithmetic circuits;
- property testing;
- polynomial characterization;
17.An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model

机译：R-Well条件模型中傅里叶变换计算的Omega（（n log n）/ R）下界
- 作者：NIR AILON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第1期
- Fourier transform;
- lower bounds;
18.Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

机译：最大和精确问题的参数化复杂性和可核化性
- 作者：STEFAN KRATSCH;DANIEL MARX;MAGNUS WAHLSTROEM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第1期
- CSP;
- kernelization;
- FPT algorithms;
- complexity characterization;
19.Complexity Hierarchies beyond Elementary

机译：超越初级的复杂性层次
- 作者：SYLVAIN SCHMITZ
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第1期
- Fast-growing complexity;
- subrecursion;
- well-quasi-order;
20.On Sample-Based Testers

机译：在基于样本的测试仪上
- 作者：ODED GOLDREICH;DANA RON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第2期
- Property Testing;
- Sampling;
21.Testing Read-Once Formula Satisfaction

机译：测试一次性公式的满意度
- 作者：ELDAR FISCHER;YONATAN GOLDHIRSH;ODED LACHISH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第2期
- Massively parametrized properties;
- property testing;
- read-once formula;
22.Tractable Parameterizations for the Minimum Linear Arrangement Problem

机译：最小线性排列问题的可牵引参数化
- 作者：MICHAEL R. FELLOWS;DANNY HERMELIN;FRANCES ROSAMOND;HADAS SHACHNAI
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第2期
23.Structural Properties of Nonautoreducible Sets

机译：非自约集的结构性质
- 作者：DUNG NGUYEN;ALAN L. SELMAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第3期
24.Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices

机译：通过偏导数矩阵的最大秩算术电路的下界
- 作者：MRINAL KUMAR;GAURAV MAHESHWARI;JAYALAL SARMA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第3期
25.A Galois Connection for Weighted (Relational) Clones of Infinite Size

机译：无限大小的加权（关系）克隆的Galois连接
- 作者：PETER FULLA;STANISLAV ZIVNY
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第3期
26.The List-Decoding Size of Fourier-Sparse Boolean Functions

机译：傅里叶稀疏布尔函数的列表解码大小
- 作者：ISHAY HAVIV;ODED REGEV
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第3期
27.Counting Homomorphisms to Square-Free Graphs, Modulo 2

机译：将同态计数到无平方图，模2
- 作者：ANDREAS GOEBEL;LESLIE ANN GOLDBERG;DAVID RICHERBY
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第3期
28.A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem

机译：拉姆西定理的平面证明的秩下界
- 作者：MASSIMO LAURIA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
- Proof complexity;
- cutting planes;
- Ramsey theory;
- rank;
- integer programming;
29.Quadratic Maps Are Hard to Sample

机译：二次映射很难采样
- 作者：EMANUELE VIOLA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
- Sampling;
- polynomials;
- extractors;
- complexity of distributions;
30.Space-Efficient Approximations for Subset Sum

机译：子集总和的空间有效逼近
- 作者：ANNA GAL;JING-TANG JANG;NUTAN LIMAYE;MEENA MAHAJAN;KARTEEK SREENIVASAIAH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
31.The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling

机译：示例的强大功能：使用组查询和条件采样的隐藏集大小近似
- 作者：DANA RON;GILAD TSUR
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
- Approximation;
- sampling;
32.Planarizing Gadgets for Perfect Matching Do Not Exist

机译：不存在用于完美匹配的平面化小工具
- 作者：ROHIT GURJAR;ARPITA KORWAR;JOCHEN MESSNER;SIMON STRAUB;THOMAS THIERAUF
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
- Parallel complexity;
- perfect matching;
- planar graphs;
33.Limitations of Deterministic Auction Design for Correlated Bidders

机译：相关投标人确定性拍卖设计的局限性
- 作者：IOANNIS CARAGIANNIS;CHRISTOS KAKLAMANIS;MARIA KYROPOULOU
- 期刊名称：《ACM Transactions on Computational Theory》 | 2016年第4期
- Optimal auction design;
- deterministic auctions;
- correlated valuations;
34.Limitations of Local Filters of Lipschitz and Monotone Functions

机译：Lipschitz和单调函数的局部滤波器的局限性
- 作者：PRANJAL AWASTHI;MADHAV JHA;MARCO MOLINARO;SOFYA RASKHODNIKOVA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第1期
- Lipschitz;
- local filter;
- monotonicity;
- privacy;
35.Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs

机译：使用协定论的内核下界：查找诱导的遗传子图
- 作者：STEFAN KRATSCH;MARCIN PILIPCZUK;ASHUTOSH RAI;VENKATESH RAMAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第1期
- Kernelization lower bounds;
- co-nondeterminism;
- hereditary graph properties;
36.Advice Lower Bounds for the Dense Model Theorem

机译：稠密模型定理的下界建议
- 作者：THOMAS WATSON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第1期
- Advice;
- dense model theorem;
- lower bounds;
37.The Complexity of the Nucleolus in Compact Games

机译：紧凑型游戏中核仁的复杂性
- 作者：GIANLUIGI GRECO;ENRICO MALIZIA;LUIGI PALOPOLI;FRANCESCO SCARCELLO
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第1期
- Game theory;
- coalitional games;
- compact representations;
- computational complexity;
- nucleolus;
- linear programming;
- solution concepts;
38.The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space

机译：合并查询和参数化对数空间的精细分类
- 作者：HUBIE CHEN;MORITZ MUELLER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第2期
- Conjunctive queries;
- graph decompositions;
- homomorphism problems;
- parameterized logarithmic space;
39.Exponential Lower Bounds for AC~0-Frege Imply Superpolynomial Frege Lower Bounds

机译：AC〜0-Frege的指数下界表示超多项式Frege下界
- 作者：YUVAL FILMUS;TONIANN PITASSI;RAHUL SANTHANAM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第2期
- Proof complexity;
40.Pebbling, Entropy, and Branching Program Size Lower Bounds

机译：Pebbling，熵和分支程序大小的下界
- 作者：BALAGOPAL KOMARATH;JAYALAL SARMA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第2期
- Pebbling games, entropy, branching programs, lower bounds;
41.Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

机译：Max-2Lin和Max-3Lin在整数，实数和大循环组上的硬度
- 作者：RYAN ODONNELL;YI WU;YUAN ZHOU
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第2期
- Max-2Lin;
- Max-3Lin;
- hardness of approximation;
- the Unique Games Conjecture;
- large alphabet sets;
42.Smoothed Complexity Theory

机译：平滑复杂度理论
- 作者：MARKUS BLAESER;BODO MANTHEY
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第2期
- Smoothed analysis;
- computational complexity;
- average-case complexity;
43.Mutual Dimension

机译：互维
- 作者：ADAM CASE;JACK H. LUTZ
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第3期
- Computable analysis;
- data processing inequality;
- effective fractal dimensions;
- Kolmogorov complexity;
- mutual information;
44.Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps

机译：使用对多项式核的参数转换来解决允许重叠的打包问题
- 作者：HENNING FERNAU;ALEJANDRO LOPEZ-ORTIZ;JAZMIN ROMERO
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第3期
- Polynomial parametric transformations;
- kernels;
- Set Packing;
- Graph Packing;
- overlap;
45.Some Hard Families of Parameterized Counting Problems

机译：参数计数问题的一些硬族
- 作者：MARK JERRUM;KITTY MEEKS
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第3期
- Counting complexity;
- parameterized complexity;
- Ramsey theory;
46.Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems

机译：汉明距离问题的确定性和量子通信复杂性的下界
- 作者：ANDRIS AMBAINIS;WILLIAM GASARCH;ARAVIND SRINIVASAN;ANDREY UTIS
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第3期
- Communication complexity;
- Hamming distance;
47.Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

机译：输入不可证明系统和P / poly的统一复杂性观点
- 作者：ODED GOLDREICH;OR MEIR
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第4期
- BPP;
- EXP;
- IP;
- MA;
- NE;
- NEXP;
- NP;
- PCP;
- P/poly;
- RP;
- E;
- ZK;
48.Exploring the Subexponential Complexity of Completion Problems

机译：探索完成问题的次指数复杂度
- 作者：PAL GRONAS DRANGE;FEDOR V. FOMIN;MICHAL PILIPCZUK;YNGVE VILLANGER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第4期
- Edge completion;
- modification;
- subexponential parameterized complexity;
49.Quantum XOR Games

机译：量子异或游戏
- 作者：ODED REGEV;THOMAS VIDICK
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第4期
- XOR games;
- entangled games;
- Grothendieck inequality;
50.On Approximate Decidability of Minimal Programs

机译：关于最小程序的大概可决定性
- 作者：JASON TEUTSCH;MARIUS ZIMAND
- 期刊名称：《ACM Transactions on Computational Theory》 | 2015年第4期
- Frequency computation;
- list approximations;
- minimal indices;
- numberings;
- Kolmogorov complexity;
51.The Hardness of Being Private

机译：私密性
- 作者：ANIL ADA;ARKADEV CHATTOPADHYAY;STEPHEN A. COOK;LILA FONTES;MICHAL KOUCKY;TONIANN PITASSI
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第1期
- Approximate privacy;
- communication complexity;
- information theory;
- privacy;
- privacy trade-off;
- Vickrey auction;
52.New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover

机译：3色和2对1标签封面的新NP硬度结果
- 作者：PER AUSTRIN;RYAN ODONNELL;LI-YANG TAN;JOHN WRIGHT
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第1期
- NP-hardness;
- constraint satisfaction problems;
- graph coloring;
- label cover;
53.Unions of Disjoint NP-Complete Sets

机译：不相交NP完全集的并集
- 作者：CHRISTIAN GLASSER;JOHN M. HITCHCOCK;A. PAVAN;STEPHAN TRAVERS
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第1期
54.On Effective Convergence of Numerical Solutions for Differential Equations

机译：关于微分方程数值解的有效收敛性
- 作者：SHU-MING SUN;NING ZHONG
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第1期
- Effective convergence;
- numerical solutions of ODEs;
55.Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)

机译：局部敏感哈希的最佳下界（q很小时除外）
- 作者：RYAN ODONNELL;YI WU;YUAN ZHOU
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第1期
- LSH;
- locality-sensitive hashing;
- Fourier analysis of boolean functions;
- noise sensitivity;
- noise stability;
56.Hard Instances of Algorithms and Proof Systems

机译：算法和证明系统的硬实例
- 作者：YIJIA CHEN;JOERG FLUM;MORITZ MUELLER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第2期
- Hard sequences;
- optimal algorithms;
- optimal proof systems;
- measure hypothesis;
57.A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing

机译：关于比较简洁表示的整数的复杂性及其在最大概率分析中的应用
- 作者：KOUSHA ETESSAMI;ALISTAIR STEWART;MIHALIS YANNAKAKIS
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第2期
58.Clique Cover and Graph Separation: New Incompressibility Results

机译：集团覆盖和图形分离：新的不可压缩结果
- 作者：MAREK CYGAN;STEFAN KRATSCH;MARCIN PILIPCZUK;MICHAL PILIPCZUK;MAGNUS WAHLSTROEM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第2期
- Kernelization;
- parameterized complexity;
- edge clique cover;
- cut problems;
59.The Complexity of Approximately Counting Tree Homomorphisms

机译：近似计数树同态的复杂性
- 作者：LESLIE ANN GOLDBERG;MARK JERRUM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第2期
- Complexity classes;
- counting problems;
- graph homomorphisms;
- reducibility;
60.Learning Hurdles for Sleeping Experts

机译：为睡眠专家学习障碍
- 作者：VARUN KANADE;THOMAS STEINKE
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第3期
- Algorithms;
- Theory;
61.(Leveled) Fully Homomorphic Encryption without Bootstrapping

机译：（分级）完全同态加密，无需引导
- 作者：ZVIKA BRAKERSKI;CRAIG GENTRY;VINOD VAIKUNTANATHAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第3期
- Security;
- Theory;
62.Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part Ⅱ

机译：2012年理论计算机科学创新特刊（第二部分）简介
- 作者：Eric Allender;Shafi Goldwasser
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第3期
63.Evolvability of Real Functions

机译：实函数的可演化性
- 作者：PAUL VALIANT
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第3期
- Algorithms;
- Theory;
64.On the One-Way Function Candidate Proposed by Goldreich

机译：关于戈德赖希提出的单向函数候选
- 作者：JAMES COOK;OMID ETESAMI;RACHEL MILLER;LUCA TREVISAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第3期
- Algorithms;
- Theory;
- Security;
65.FPT is Characterized by Useful Obstruction Sets: Connecting Algorithms, Kernels, and Quasi-Orders

机译：FPT的特征在于有用的障碍集：连接算法，内核和拟序
- 作者：MICHAEL R. FELLOWS;BART M. P. JANSEN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第4期
- Kernelization;
- parameterized complexity;
- pathwidth;
- well-quasi-ordering;
66.The Complexity of the Comparator Circuit Value Problem

机译：比较器电路值问题的复杂性
- 作者：STEPHEN A. COOK;YUVAL FILMUS;DAI TRI MAN LE
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第4期
- Comparator circuits;
- P-completeness;
67.The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2

机译：仙人掌图模2同态计数的复杂性
- 作者：ANDREAS GOEBEL;LESLIE ANN GOLDBERG;DAVID RICHERBY
- 期刊名称：《ACM Transactions on Computational Theory》 | 2014年第4期
- Graph homomorphism;
- cactus graph;
- counting modulo 2;
- parity complexity dichotomy;
68.On the Usefulness of Predicates

机译：论谓词的有用性
- 作者：PER AUSTRIN;JOHAN HAESTAD
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第1期
- Constraint satisfaction problem;
- usefulness;
- approximation resistance;
- unique games conjecture;
69.Verifying Proofs in Constant Depth

机译：验证恒定深度的证明
- 作者：OLAF BEYERSDORFF;SAMIR DATTA;ANDREAS KREBS;MEENA MAHAJAN;GIDO SCHARFENBERGER-FABIAN;KARTEEK SREENIVASAIAH;MICHAEL THOMAS;HERIBERT VOLLMER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第1期
- Proof complexity;
- Proof circuits;
- small depth proofs;
- circuit complexity;
70.On Multiway Cut Parameterized Above Lower Bounds

机译：在下界上方参数化的多路切割中
- 作者：MAREK CYGAN;MARCIN PILIPCZUK;MICHAL PILIPCZUK;JAKUB ONUFRY WOJTASZCZYK
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第1期
- Fixed parameter tractability;
- linear programming;
- multiway cut;
- parameterized algorithms;
71.Economical Caching

机译：经济缓存
- 作者：MATTHIAS ENGLERT;HEIKO ROEGLIN;JACOB SPOENEMANN;BERTHOLD VOECKING
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第2期
- Competitive analysis;
- online algorithms;
- storage management;
72.On Approximating the Number of Relevant Variables in a Function

机译：关于函数中相关变量数的逼近
- 作者：DANA RON;GILAD TSUR
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第2期
- Property testing;
73.Hard Functions for Low-Degree Polynomials over Prime Fields

机译：素数域上低度多项式的硬函数
- 作者：ANDREJ BOGDANOV;AKINORI KAWACHI;HIDETOKI TANAKA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第2期
- Hardness amplification;
- low-degree polynomials;
- property testing;
74.Alternation-Trading Proofs, Linear Programming, and Lower Bounds

机译：交替交易证明，线性规划和下界
- 作者：RYAN WILLIAMS
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第2期
- Alternation;
- time-space trade-offs;
- lower bounds;
- linear programming;
75.Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012

机译：2012年理论计算机科学创新特刊简介
- 作者：Eric Allender;Shafi Goldwasser
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第3期
76.Linear-Time Decoding of Regular Expander Codes

机译：常规扩展码的线性时间解码
- 作者：MICHAEL VIDERMAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第3期
- Error-correcting codes;
- LDPC codes;
- expander codes;
- decoding;
77.High-Confidence Predictions under Adversarial Uncertainty

机译：对抗不确定性下的高可信度预测
- 作者：ANDREW DRUCKER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第3期
- Prediction;
- worst-case prediction;
- binary sequences;
78.Compressed Matrix Multiplication

机译：压缩矩阵乘法
- 作者：RASMUS PAGH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第3期
- Matrix multiplication;
- approximation;
- sparse recovery;
79.Quantum Rejection Sampling

机译：量子排斥采样
- 作者：MARIS OZOLS;MARTIN ROETTELER;JEREMIE ROLAND
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第3期
- Quantum algorithms;
- rejection sampling;
- query complexity;
- quantum Metropolis sampling;
- Boolean hidden shift problem;
80.Graph Isomorphism is Not AC~0-Reducible to Group Isomorphism

机译：图同构不能AC〜0还原为组同构
- 作者：ARKADEV CHATTOPADHYAY;JACOBO TORAN;FABIAN WAGNER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Complexity;
- algorithms;
- isomorphism problems;
- limited nondeterminism;
81.Real Advantage

机译：真正的优势
- 作者：ALEXANDER RAZBOROV;EMANUELE VIOLA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Lower bounds;
- correlation bounds;
- polynomials;
- parity;
82.Explicit Optimal Hardness via Gaussian Stability Results

机译：通过高斯稳定性结果显示最佳硬度
- 作者：ANINDYA DE;ELCHANAN MOSSEL
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Gaussian stability;
- dictatorship test;
- unique games conjecture;
83.Robust Satisfiability for CSPs: Hardness and Algorithmic Results

机译：CSP的强大可满足性：硬度和算法结果
- 作者：VICTOR DALMAU;ANDREI KROKHIN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Constraint satisfaction problem;
- approximation algorithms;
- universal algebra;
- homomorphism duality;
84.Distortion is Fixed Parameter Tractable

机译：失真是固定参数可处理的
- 作者：MICHAEL FELLOWS;FEDOR V. FOMIN;DANIEL LOKSHTANOV;ELENA LOSIEVSKAJA;FRANCES ROSAMOND;SAKET SAURABH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Embedding;
- distortion;
- tree;
- parameterized algorithms;
85.Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds

机译：精确的学习算法，博彩游戏和巡回赛下限
- 作者：RYAN C. HARKINS;JOHN M. HITCHCOCK
- 期刊名称：《ACM Transactions on Computational Theory》 | 2013年第4期
- Theory;
86.Exact Quantum Algorithms for the Leader Election Problem

机译：领导者选举问题的精确量子算法
- 作者：SEIICHIRO TANI;HIROTADA KOBAYASHI;KEIJI MATSUMOTO
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第1期
- distributed computing;
- quantum algorithms;
- quantum communication;
87.Approximating Linear Threshold Predicates

机译：近似线性阈值谓词
- 作者：MAHDI CHERAGHCHI;JOHAN HASTAD;MARCUS ISAKSSON;OLA SVENSSON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第1期
- approximation algorithms;
- constraint satisfactory problems;
- linear;
- threshold predicates;
88.Extractors and Lower Bounds for Locally Samplable Sources

机译：本地可简化源的提取器和下界
- 作者：ANINDYA DE;THOMAS WATSON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第1期
- extractors;
- lower bounds;
- locally samplable sources;
89.The Computational Complexity of Nash Equilibria in Concisely Represented Games

机译：简洁表示游戏中纳什均衡的计算复杂性
- 作者：GRANT R. SCHOENEBECK;SALIL VADHAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第2期
- nash equilibrium;
- concise games;
- graph games;
- circuit games;
- computational game theory;
90.Complexity Theory for Operators in Analysis

机译：分析中的运营商复杂性理论
- 作者：AKITOSHI KAWAMURA;STEPHEN COOK
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第2期
- computable analysis;
- computational complexity;
- higher-type complexity;
- second-order polynomials;
91.Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions

机译：通过验证产生最佳解决方案的防串谋机制
- 作者：PAOLO PENNA;CARMINE VENTRE
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第2期
- game theory;
- algorithmic mechanism design;
- collusion;
92.Parameterized Bounded-Depth Frege Is not Optimal

机译：参数化的边界深度镶边不是最佳的
- 作者：OLAF BEYERSDORFF;NICOLA GALESI;MASSIMO LAURIA;ALEXANDER A. RAZBOROV
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第3期
- proof complexity;
- parameterized complexity;
- resolution;
- bounded-depth frege;
93.Relativized Worlds without Worst-Case to Average-Case Reductions for NP

机译：NP没有最坏情况到平均情况减少的相对化世界
- 作者：THOMAS WATSON
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第3期
- average-case complexity;
- oracles;
94.On the Sum of Square Roots of Polynomials and Related Problems

机译：多项式平方根之和及相关问题
- 作者：NEERAJ KAYAL;CHAN DAN SAHA
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第4期
- sum of square roots;
- arithmetic circuits;
- polynomials;
95.A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs

机译：恒圆Arthur-Merlin证明的并行重复定理
- 作者：RAFAEL PASS;MUTHURAMAKRISHNAN VENKITASUBRAMANIAM
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第4期
- interactive proofs;
- parallel-repetition;
- soundness error;
- public-coin protocols;
96.Approximating the Influence of Monotone Boolean Functions in O(n~(1/2)) Query Complexity

机译：近似单调布尔函数对O（n〜（1/2））查询复杂度的影响
- 作者：DANA RON;RONITT RUBINFELD;MULI SAFRA;ALEX SAMORODNITSKY;OMRI WEINSTEIN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第4期
- influence of a boolean function;
- sublinear query approximation algorithms;
- symmetric chains;
97.On the Computational Complexity of Stochastic Controller Optimization in POMDPs

机译：POMDP中随机控制器优化的计算复杂性
- 作者：NIKOS VLASSIS;MICHAEL L. LITTMAN;DAVID BARBER
- 期刊名称：《ACM Transactions on Computational Theory》 | 2012年第4期
98.Kolmogorov Complexity in Randomness Extraction

机译：随机抽取中的Kolmogorov复杂度
- 作者：JOHN M. HITCHCOCK;A. PAVAN;N. V. VINODCHANDRAN
- 期刊名称：《ACM Transactions on Computational Theory》 | 2011年第1期
- randomness;
- extractors;
- kolmogorov complexity;
99.On the Power of Isolation in Planar Graphs

机译：平面图中的隔离度
- 作者：RAGHAV KULKARNI
- 期刊名称：《ACM Transactions on Computational Theory》 | 2011年第1期
- isolating lemma;
- planar graphs;
- perfect matching;
- NL;
- NC;
100.Approximate Query Complexity

机译：近似查询复杂度
- 作者：CLIFFORD SMYTH
- 期刊名称：《ACM Transactions on Computational Theory》 | 2011年第1期

客服邮箱：kefu@zhangqiaokeyan.com

客服微信
服务号