首页>外文期刊>Electronic Colloquium on Computational Complexity

Electronic Colloquium on Computational Complexity

Electronic Colloquium on Computational Complexity

中文名称：在计算复杂度电子讨论会

ISSN：1433-8092
出版周期：-

发文量：2964

期刊论文

年度选择

2020
- 第1期
- 第a期
2019
- 第3期
- 第4期
- 第118期
- 第136期
2018
- 第3期
- 第4期
- 第9期
- 第118期
- 第136期
- 第202期
2017
- 第4期
- 第118期
- 第131期
- 第136期
- 第202期
2016
- 第8期
- 第118期
- 第126期
- 第136期
- 第202期
2015
- 第4期
- 第126期
- 第131期
- 第136期
- 第202期
2014
- 第118期
- 第126期
- 第136期
2013
- 第4期
- 第126期
- 第131期
- 第136期
2012
- 第3期
- 第5期
- 第118期
- 第131期
- 第136期
- 第195期
2011
- 第1期
- 第118期
- 第131期
- 第136期
- 第202期
2010
- 第3期
- 第4期
- 第118期
- 第136期
- 第195期
2009
- 第1期
- 第19期
- 第131期
- 第134期
- 第136期
2003
- 第1期
- 第118期
- 第126期
- 第131期
2002
- 第3期
- 第121期
- 第126期
2001
- 第1期
- 第3期
- 第118期
- 第121期
2000
- 第3期
- 第9期
- 第131期
1999
- 第9期
- 第131期
1998
- 第4期
- 第131期
1997
- 第4期
- 第202期
1996
- 第126期
- 第202期
1995
- 第195期
- 第202期
1994
- 第195期

更多>>

全选（0）

1.A Lower Bound for Relaxed Locally Decodable Codes

机译：宽松的本地可解码代码的下界
- 作者：Tom Gur;Oded Lachish
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
2.The complexity of 3-colouring H -colourable graphs

机译：H色3色图的复杂性
- 作者：Andrei Krokhin;Jakub Opr?al
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- constraint satisfactiongraph homomorphismpromise problems;
3.NP-Completeness, Proof Systems, and Disjoint NP-Pairs

机译：NP完整性，证明系统和不相交的NP对
- 作者：Titus Dose;Christian Gla?er
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- disjoint NP-pairNP-completeoraclePropositional Proof System;
4.Simplified inpproximability of hypergraph coloring via t-agreeing families

机译：通过t同意族简化了超图染色的不可逼近性
- 作者：Per Austrin;Amey Bhangale;Aditya Potukuchi
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- hypergraph coloringintersecting families;
5.On -sensitive monotone computations

机译：敏感单调计算
- 作者：Pavel Hrubes
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Arithemtic Circuitsnon-negative rank;
6.Counting basic-irreducible factors mod p k in deterministic poly-time and p -adic applications

机译：在确定性的多元时间和p-adic应用中计算基本不可约因子mod p k
- 作者：Ashish Dwivedi;Rajat Mittal;Nitin Saxena
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- basic irreduciblecountingdeterministicmoduloprime-powerroottreeunramified;
7.Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

机译：对于ACC电路，不确定的拟多项式时间是平均情况下的难点
- 作者：Lijie Chen
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
8.Smooth and Strong PCPs

机译：平滑而强大的PCP
- 作者：Orr Paradise
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
9.AC0[p] Lower Bounds against MCSP via the Coin Problem

机译：通过硬币问题，AC0 [p]对MCSP的下界
- 作者：Alexander Golovnev;Rahul Ilango;Russell Impagliazzo;Valentine Kabanets;Antonina Kolokolova;Avishay Tal
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- AC0pbiased random boolean functionscircuit lower boundscoin problemhybrid argumentMinimum Circuit Size Problem (MCSP)MKTP;
10.Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

机译：没有禁止子图和几乎不平衡的扩展器的采样图
- 作者：Benny Applebaum;Eliran Kachlon
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
11.Strategy-Stealing is Non-Constructive

机译：策略窃取是非建设性的
- 作者：Greg Bodwin;Ofer Grossman
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Combinatorial GamesPSPACE-completenessstrategy stealing;
12.A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

机译：超图的分离定理和CSP-SAT算法
- 作者：Michal Koucky;Vojtech Rodl;Navid Talebanfard
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- CSPhypergraphsatisfiability algorithmSeparatorSETH;
13.Pseudo-deterministic Streaming

机译：伪确定性流
- 作者：Shafi Goldwasser;Ofer Grossman;Sidhanth Mohanty;David Woodruff
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- pseudo-deterministicStreaming Algorithms;
14.On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

机译：关于指数时间假设，非随机化和电路下界
- 作者：Lijie Chen;Ron Rothblum;Roei Tell;Eylon Yogev
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- circuit lower boundsderadomizationexponential-time hypothesis;
15.Beyond Natural Proofs: Hardness Magnification and Locality

机译：超越自然证明：硬度放大率和局部性
- 作者：Igor Carboni Oliveira;Lijie Chen;Shuichi Hirahara;Ján Pich;Ninad Rajgopal;Rahul Santhanam
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- circuit complexityhardness magnificationlearning algorithmslocal computationnatural proofs;
16.Almost Optimal Testers for Concise Representations

机译：简洁表示形式的最佳测试仪
- 作者：Nader Bshouty
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
17.Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity

机译：Ar？kan与Shannon会合：极化码，信道容量接近最佳收敛
- 作者：Venkatesan Guruswami;Andrii Riazanov;Min Ye
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
18.Log-Seed Pseudorandom Generators via Iterated Restrictions

机译：通过迭代限制的对数种子伪随机数生成器
- 作者：Dean Doron;Pooya Hatami;William Hoza
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- constant depth formulasexplicit constructionsPseudorandom generaorsread-once formulassymmetric polynomials;
19.An Adaptive Step Toward the Multiphase Conjecture

机译：迈向多相猜想的自适应步骤
- 作者：Young Ko;Omri Weinstein
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
20.d -to- 1 Hardness of Coloring 4 -colorable Graphs with O (1) colors

机译：d到1的着色难度4种具有O（1）颜色的可着色图形
- 作者：Venkatesan Guruswami;Sai Sandeep
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- graph coloringInapproximabilitymarkov chainmatrix scalingPCP;
21.A note on the relation between XOR and Selective XOR Lemmas

机译：关于XOR与选择性XOR引理之间的关系的注释
- 作者：Ragesh Jaiswal
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- XOR Lemmas;
22.Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

机译：可逆的卵石游戏以及类树与一般分辨率空间之间的关系
- 作者：Jacobo Toran;Florian W?rz
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Clause Spacepebble gameProof ComplexityProver-Delayer GameRaz-McKenzie GameResolutionreversible pebblingtree-like resolutionVariable Space;
23.Resolution Lower Bounds for Refutation Statements

机译：解决驳回声明的下界
- 作者：Michal Garlik
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- reflection principlesrefutation statementsResolution;
24.Approximate degree, secret sharing, and concentration phenomena

机译：近似程度，秘密共享和集中现象
- 作者：Andrej Bogdanov;Nikhil Mande;Justin Thaler;Christopher Williamson
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- approximate degreedual polynomialssecret sharing;
25.Average Bias and Polynomial Sources

机译：平均偏差和多项式源
- 作者：Arnab Bhattacharyya;Philips George John;Suprovat Ghoshal;Raghu Meka
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
26.Pseudo-Mixing Time of Random Walks

机译：随机游走的伪混合时间
- 作者：Itai Benjamini;Oded Goldreich
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Caylay graphsmixing timeone-way functionPseudorandomnessrandom walks on graphs;
27.Parity helps to compute Majority

机译：奇偶校验有助于计算多数
- 作者：Igor Carboni Oliveira;Rahul Santhanam;Srikanth Srinivasan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- circuit complexitylower boundsmajorityparity gatepolynomial approximation;
28.Bounded-depth Frege complexity of Tseitin formulas for all graphs

机译：所有图形的Tseitin公式的有界深度弗雷格复杂度
- 作者：Nicola Galesi;Dmitry Itsykson;Artur Riazanov;Anastasia Sofronova
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
29.Randomness and Intractability in Kolmogorov Complexity

机译：Kolmogorov复杂性的随机性和难处理性
- 作者：Igor Carboni Oliveira
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- circuit complexityKolmogorov complexitylower boundsPseudorandomness;
30.andom walks and forbidden minors II: A poly ( d eps ? 1 ) -query tester for minor-closed properties of bounded degree graphs

机译：随机游走和禁止的未成年人II：A poly（d eps？1）-查询测试器，用于有限度图的次闭合特性
- 作者：Akash Kumar;C. Seshadhri;Andrew Stolman
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
31.DEEP-FRI: Sampling Outside the Box Improves Soundness

机译：DEEP-FRI：盒子外面的采样提高了声音的响度
- 作者：Eli Ben-Sasson;Lior Goldberg;Swastik Kopparty;Shubhangi Saraf
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
32.Quantum hardness of learning shallow classical circuits

机译：学习浅层经典电路的量子硬度
- 作者：Srinivasan Arunachalam;Alex Bredariol Grilo;Aarthi Sundaram
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- constant-depth circuitLearning theorylearning with errorsPseudo-Random GeneratorsQuantum Computation;
33.Statistical Difference Beyond the Polarizing Regime

机译：极化体制之外的统计差异
- 作者：Itay Berman;Akshay Degwekar;Ron D. Rothblum;Prashant Nalini Vasudevan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
34.A C 0 [ p ] Lower Bounds and NP-Hardness for Variants of MCSP

机译：MCSP变体的C 0 [p]下界和NP硬度
- 作者：Rahul Ilango
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- AC0pcircuit lower boundsconstant depth formulasMinimum Circuit Size Problem (MCSP)NP-completeness;
35.On Tseitin formulas, read-once branching programs and treewidth

机译：在Tseitin公式，一次性分支程序和树宽上
- 作者：Ludmila Glinskih;Dmitry Itsykson
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
36.Fourier bounds and pseudorandom generators for product tests

机译：用于产品测试的傅立叶界和伪随机发生器
- 作者：Chin Ho Lee
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- bounded independence plus noiseFourier spectrumproduct testpseudorandom generators;
37.Upper Bounds on Communication in terms of Approximate Rank

机译：大致排名方面的沟通上限
- 作者：Anna Gal;Ridwan Syed
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
38.Towards Optimal Separations between Quantum and Randomized Query Complexities

机译：寻求量子和随机查询复杂度之间的最佳分离
- 作者：Avishay Tal
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
39.On Prover-Efficient Public-Coin Emulation of Interactive Proofs

机译：关于交互式证明的证明有效的公共硬币模拟
- 作者：Gal Arnon;Guy Rothblum
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
40.Extractor Lower Bounds, Revisited

机译：再探提取器下界
- 作者：Divesh Aggarwal;Siyao Guo;Maciej Obremski;Joao Ribeiro;Noah Stephens-Davidowitz
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Fourier analysislower boundsRandomness Extractors;
41.The Random-Query Model and the Memory-Bounded Coupon Collector

机译：随机查询模型和内存绑定优惠券收集器
- 作者：Ran Raz;Wei Zhan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- branching programsrandom-query modeltime-space trade-offs;
42.Hardness of Learning DNFs using Halfspaces

机译：使用半空间学习DNF的难度
- 作者：Suprovat Ghoshal;Rishi Saket
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- DNF formulasHalfspacesInapproximabilitylearning;
43.SETH-hardness of Coding Problems

机译：SETH编码问题的难度
- 作者：Noah Stephens-Davidowitz;Vinod Vaikuntanathan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- exponential-time hypothesisminimum distance problemnearest codeword problemSETH;
44.How QBF Expansion Makes Strategy Extraction Hard

机译：QBF扩展如何使策略提取变得困难
- 作者：Leroy Chew;Judith Clymo
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- Feasible InterpolationQBFStrategy extraction;
45.Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

机译：搜索关于代数复杂度，GCT和不变环的生成器硬度的问题。
- 作者：Ankit Garg;Visu Makam;Rafael Mendes de Oliveira;Avi Wigderson
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2019年第136期
- algebraic complexitygeometric complexity theoryInvariant theorylower boundsrepresentation theory;
46.Lower bounds on information complexity via zero-communication protocols and applications

机译：通过零通信协议和应用程序降低信息复杂性的界限
- 作者：Iordanis Kerenidis;Sophie Laplante;Virginie Lerays;Jérémie Roland;David Xiao
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
47.Testing Assignments of Boolean CSPs

机译：测试布尔CSP的分配
- 作者：Arnab Bhattacharyya;Yuichi Yoshida
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
48.Query Complexity and Error Tolerance of Witness Finding Algorithms

机译：证人查找算法的查询复杂度和容错能力
- 作者：Akinori Kawachi;Benjamin Rossman;Osamu Watanabe
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
49.Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

机译：多方通信中的张量秩和强量子不确定性
- 作者：Marcos Villagra;Masaki Nakanishi;Shigeru Yamashita;Yasuhiko Nakashima
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
50.On the Power of Conditional Samples in Distribution Testing

机译：论条件样本在分布测试中的作用
- 作者：Sourav Chakraborty;Eldar Fischer;Yonatan Goldhirsh;Arie Matsliah
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
51.On Approximation Lower Bounds for TSP with Bounded Metrics

机译：具有约束度量的TSP的近似下界
- 作者：Marek Karpinski;Richard Schmied
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
52.Quantum-Secure Message Authentication Codes

机译：量子安全消息身份验证码
- 作者：Dan Boneh;Mark Zhandry
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
53.A Note on Subspace Evasive Sets

机译：关于子空间逃避集的注记
- 作者：Avraham Ben-Aroya;Igor Shinkar
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
54.A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

机译：完整二元基础上公式的可满足性算法和平均情况硬度
- 作者：Kazuhisa Seto;Suguru Tamaki
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
55.Information lower bounds via self-reducibility

机译：通过自我简化实现信息下限
- 作者：Mark Braverman;Ankit Garg;Denis Pankratov;Omri Weinstein
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
56.New affine-invariant codes from lifting

机译：解除了新的仿射不变代码
- 作者：Alan Guo;Swastik Kopparty;Madhu Sudan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
57.Combinatorial limitations of a strong form of list decoding

机译：列表解码的强大形式的组合限制
- 作者：Venkatesan Guruswami;Srivatsan Narayanan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
58.Better pseudorandom generators from milder pseudorandom restrictions

机译：来自较温和的伪随机限制的更好的伪随机生成器
- 作者：Parikshit Gopalan;Raghu Meka;Omer Reingold;Luca Trevisan;Salil Vadhan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
59.Limits of provable security for homomorphic encryption

机译：同态加密可证明的安全性限制
- 作者：Andrej Bogdanov;Chin Ho Lee
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
60.Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

机译：CNF布尔公式的句法同构是图同构完成
- 作者：Giorgio Ausiello;Francesco Cristiano;Luigi Laura
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
61.On the Circuit Complexity of Composite Galois Field Transformations

机译：复合伽罗瓦场变换的电路复杂性
- 作者：Charanjit Jutla;Vijay Kumar;Atri Rudra
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
62.Properties and Applications of Boolean Function Composition

机译：布尔函数组合的性质和应用
- 作者：Avishay Tal
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
63.Clique Problem, Cutting Plane Proofs, and Communication Complexity

机译：派系问题，裁断面证明和沟通复杂性
- 作者：Stasys Jukna
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
64.The Freiman-Ruzsa Theorem in Finite Fields

机译：有限域中的弗赖曼-鲁兹定理
- 作者：Chaim Even-Zohar;Shachar Lovett
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
65.On Rigid Matrices and Subspace Polynomials

机译：关于刚性矩阵和子空间多项式
- 作者：Noga Alon;Gil Cohen
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
66.Lower bounds for myopic DPLL algorithms with a cut heuristic

机译：具有割试法的近视DPLL算法的下限
- 作者：Dmitry Itsykson;Dmitry Sokolov
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
67.Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

机译：Kolmogorov的复杂性，电路和算术形式理论的强度
- 作者：Eric Allender;George Davie;Luke Friedman;Samuel Hopkins;Iddo Tzameret
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
68.Lattice Variant of the Sensitivity Conjecture

机译：灵敏度猜想的格变式
- 作者：Meena Boppana
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
69.On the correlation of parity and small-depth circuits

机译：关于奇偶校验和小深度电路的相关性
- 作者：Johan Hastad
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
70.A Combinatorial Characterization of smooth LTCs and Applications

机译：平滑LTC的组合特征及其应用
- 作者：Eli Ben-Sasson;Michael Viderman
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
71.Computing Bounded Path Decompositions in Logspace

机译：计算Logspace中的有界路径分解
- 作者：Shiva Kintali;Sinziana Munteanu
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
72.Testing Similar Means

机译：测试相似的手段
- 作者：Reut Levi;Dana Ron;Ronitt Rubinfeld
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
73.Rank Bounds for a Hierarchy of Lov'{a}sz and Schrijver

机译：Lov '{a} sz和Schrijver层次结构的等级界
- 作者：Pratik Worah
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
74.Languages with Efficient Zero-Knowledge PCPs are in SZK

机译：具有高效零知识PCP的语言为SZK
- 作者：Mohammad Mahmoody;David Xiao
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
75.On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

机译：关于概率可检验证明的具体效率阈值
- 作者：Eli Ben-Sasson;Alessandro Chiesa;Daniel Genkin;Eran Tromer
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
76.Some definitorial suggestions for parameterized proof complexity

机译：有关参数化证明复杂性的一些最终建议
- 作者：Joerg Flum;Moritz Müller
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
77.Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

机译：严格限制宽度至少为4的可满足谓词的近似抗性，绕开d比1
- 作者：Cenny Wenner
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
78.On the Effect of the Proximity Parameter on Property Testers

机译：接近参数对性能测试器的影响
- 作者：Oded Goldreich
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
79.Query complexity of matroids

机译：拟阵的查询复杂度
- 作者：Raghav Kulkarni;Miklos Santha
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
80.Explicit Optimal hardness via Gaussian stability results

机译：通过高斯稳定性结果显示最佳硬度
- 作者：Anindya De;Elchanan Mossel
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
81.Faster SDP hierarchy solvers for local rounding algorithms

机译：用于本地舍入算法的更快的SDP层次求解器
- 作者：Venkatesan Guruswami;Ali Kemal Sinop
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
82.Noncommutativity makes determinants hard

机译：非交换性使行列式很难
- 作者：Markus Bl?ser
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
83.Packing Edge-Disjoint Triangles in Given Graphs

机译：在给定图中填充边缘不相交的三角形
- 作者：Tomas Feder;Carlos Subi
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
84.Sparse affine-invariant linear codes are locally testable

机译：稀疏仿射不变线性码可本地测试
- 作者：Eli Ben-Sasson;Noga Ron-Zewi;Madhu Sudan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
85.The Inverse Shapley Value Problem

机译：Shapley逆值问题
- 作者：Anindya De;Ilias Diakonikolas;Rocco Servedio
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
86.Two-Sided Error Proximity Oblivious Testing

机译：双向误差近似测试
- 作者：Oded Goldreich;Igor Shinkar
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2012年第5期
87.Reducibility Among Fractional Stability Problems

机译：分数稳定性问题中的可约性
- 作者：Shiva Kintali;Laura J Poplawski;Rajmohan Rajaraman;Ravi Sundaram;Shang-Hua Teng
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
88.From absolute distinguishability to positive distinguishability

机译：从绝对可分辨性到积极可分辨性
- 作者：Zvika Brakerski;Oded Goldreich
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
89.Direct Sums in Randomized Communication Complexity

机译：随机通信复杂度的直接求和
- 作者：Boaz Barak;Mark Braverman;Xi Chen;Anup Rao
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
90.Equivalence of Uniform Key Agreement and Composition Insecurity

机译：统一密钥协议的等效性和组合不安全性
- 作者：Chongwon Cho;Chen-Kuei Lee;Rafail Ostrovsky
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
91.The intersection of two halfspaces has high threshold degree

机译：两个半空间的交点具有高阈值度
- 作者：Alexander A. Sherstov
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
92.On the Power of Isolation in Planar Structures

机译：平面结构中的隔离力
- 作者：Raghav Kulkarni
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
93.Composition of low-error 2-query PCPs using decodable PCPs

机译：使用可解码PCP组成低错误2查询PCP
- 作者：Irit Dinur;Prahladh Harsha
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
94.One-Way Functions and the Isomorphism Conjecture

机译：单向函数和同构猜想
- 作者：Agrawal Manindra;Osamu Watanabe
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2009年第19期
95.Limits on the rate of locally testable affine-invariant codes

机译：局部可测试仿射不变代码率的限制
- 作者：Eli Ben-Sasson;Madhu Sudan
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期
96.Symmetric LDPC codes are not necessarily locally testable

机译：对称LDPC码不一定在本地可测试
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期
97.On the Minimal Fourier Degree of Symmetric Boolean Functions

机译：关于对称布尔函数的最小傅里叶级数
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期
98.Bypassing UGC from some optimal geometric inapproximability results

机译：从某些最佳几何不可逼近结果绕过UGC
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期
99.Weak Kernels

机译：弱核
- 作者：Haitao Jiang;Binhai Zhu
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期
100.On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

机译：多项式恒等式检验与寻找变量不相交因子之间的关系
- 作者：Amir Shpilka;Ilya Volkovich
- 期刊名称：《Electronic Colloquium on Computational Complexity》 | 2010年第3期

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有出版物经营许可证

客服微信
服务号