Computational Complexity

Journal Title：Computational Complexity

computational complexity presents outstanding research in computational complexity. Its subject is at the interface between mathematics and theoretical computer science, with a clear mathematical profile and strictly mathematical format.

The central topics are:

Models of computation, complexity bounds (with particular emphasis on lower bounds), complexity classes, trade-off results

for sequential and parallel computation

for "general" (Boolean) and "structured" computation (e.g. decision trees, arithmetic circuits)

for deterministic, probabilistic, and nondeterministic computation

worst case and average case

Specific areas of concentration include:

Structure of complexity classes (reductions, relativization questions, degrees, derandomization)

Algebraic complexity (bilinear complexity, computations for polynomials, groups, algebras, and representations)

Interactive proofs, pseudorandom generation, and randomness extraction

Complexity issues in:

crytography

learning theory

number theory

logic (complexity of logical theories, cost of decision procedures)

combinatorial optimization and approximate Solutions

distributed computing

property testing.

计算复杂性展示了计算复杂性方面的杰出研究。其主题是数学和理论计算机科学的交叉学科，具有清晰的数学特征和严格的数学格式。

中心主题是：

计算模型、复杂度界限（特别强调下限）、复杂度类别、权衡结果

用于顺序和并行计算

用于“一般”（布尔）和“结构化”计算（例如决策树、算术电路）

用于确定性、概率和非确定性计算

最坏情况和平均情况

具体集中领域包括：

复杂度类别的结构（归约、相对化问题、度数、去随机化）

代数复杂度（双线性复杂度、多项式、群、代数和表示的计算）

交互式证明、伪随机生成和随机性提取

复杂性问题：

密码学

学习理论

数论

逻辑（逻辑理论的复杂性、决策程序的成本）

组合优化和近似解

分布式计算

属性测试。

Computational Complexity创刊于1991年，由Springer International Publishing出版商出版，收稿方向涵盖数学 - 计算机：理论方法全领域，此刊是中等级别的SCI期刊，所以过审相对来讲不是特别难，但是该刊专业认可度不错，仍然是一本值得选择的SCI期刊 。平均审稿速度 12周，或约稿 ，影响因子指数0.7，该期刊近期没有被列入国际期刊预警名单，广大学者值得一试。