计算复杂性提出了计算复杂性方面的杰出研究。它的主题是数学和理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。中心主题是：计算模型、复杂性界限（特别强调下界）、复杂性类别、权衡结果用于确定性、概率性和非确定性计算的“一般”（布尔）和“结构化”计算（例如决策树、算术电路）的顺序和并行计算最坏情况和平均情况的具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）代数复杂性（双线性复杂性，多项式、组、代数和表示的计算）交互式证明、伪随机生成和随机性提取复杂性问题：密码学学习理论数论逻辑（逻辑理论的复杂性，决策过程的成本）组合优化和近似解分布式计算性能测试。

The journal 'Computational Complexity' is dedicated to outstanding research in the field of computational complexity, focusing on the interface between mathematics and theoretical computer science, characterized by clear mathematical outlines and rigorous mathematical formats. The central themes include computational models, complexity bounds (with a particular emphasis on lower bounds), complexity classes, and trade-off results for deterministic, probabilistic, and non-deterministic computations. Specific areas of focus include: the structure of complexity classes (simplification, relativization problems, degrees, derandomization), algebraic complexity (bilinear complexity, computations of polynomials, groups, algebras, and representations), interactive proofs, pseudorandom generation, and randomness extraction. Complexity issues encompass cryptography, learning theory, number theory, logic (the complexity of logical theories, costs of decision processes), combinatorial optimization and approximate solutions, as well as performance testing in distributed computing.

《Computational Complexity》期刊致力于计算复杂性领域的杰出研究，涵盖数学与理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。其核心主题包括计算模型、复杂性界限（特别是下界）、复杂性类别，以及用于确定性、概率性和非确定性计算的权衡结果。具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）、代数复杂性（双线性复杂性、多项式、组、代数和表示的计算）、交互式证明、伪随机生成和随机性提取。复杂性问题涉及密码学、学习理论、数论、逻辑（逻辑理论的复杂性、决策过程的成本）、组合优化和近似解，以及分布式计算性能测试。

Computational Complexity

Abstract The currently fastest known algorithm for k -SAT is PPSZ, named after its inventors (Paturi et al. in J ACM 52(3):337-364, 2005. http://dx.doi.org/10.1145/1066100.1066101 ). Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify the analysis of Hertli (in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, Los Alamitos, 2011) for input formulas with multiple satisfying assignments. Second, we show a “lifting result”: if you improve PPSZ for k -CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k -CNF formulas. In combination this with results by Hansen et al. (in Charikar and Cohen (ed) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019) and Scheder (in 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021), who all prove improved time bounds for Unique- k -SAT, this gives improved bounds for general k -SAT. We also generalize our results to the domain of Constraint Satisfaction Problems, i.e., satisfiability with more than two truth values.

Dominik Scheder

John Steinberger

PPSZ for General k-SAT and CSP—Making Hertli’s Analysis Simpler and 3-SAT Faster

PPSZ 用于一般 k-SAT 和 CSP——简化 Hertli 的分析并加快 3-SAT 速度

View ann-vertex,m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with thelengths of random walks on the graph. For example, thecommute time between two verticess andt (the expected length of a random walk froms tot and back) is precisely characterized by the effective resistanceR st betweens andt: commute time=2mR st . As a corollary, thecover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistanceR in the graph to within a factor of logn:mR<-cover time<-O(mRlogn). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, we improve known bounds on cover times for high-degree graphs and expanders, and give new proofs of known results for multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

Ashok K. Chandra

Prabhakar Raghavan

Walter L. Ruzzo

Roman Smolensky

Prasoon Tiwari

The electrical resistance of a graph captures its commute and cover times

图的电阻与其通勤时间和覆盖时间的关系

Authors would like to correct the error in their publication.

Orr Paradise

Correction to: Smooth and Strong PCPs

更正：平滑且强健的PCP

Toniann Pitassi

Morgan Shirley

Thomas Watson

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

通信复杂性中的非确定性和随机布尔层次结构

Abstract We study the approximation of halfspaces $$h:\{0,1\}^n\to\{0,1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>h</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>→</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:math> in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus $$2^{-\Omega(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>-</mml:mo> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus $$\Omega(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k -party number-on-the-forehead model, where we obtain an explicit separation of log n versus $$\Omega(n/4^{n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>4</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for communication with unbounded versus weakly unbounded error.

Alexander A. Sherstov

The hardest halfspace

最难的半空间

Abstract We use the approximation method of Razborov to analyze the locality barrier which arose from the investigation of the hardness magnification approach to complexity lower bounds. Adapting a limitation of the approximation method obtained by Razborov, we show that in many cases it is not possible to combine the approximation method with typical (localizable) hardness magnification theorems to derive strong circuit lower bounds. In particular, one cannot use the approximation method to derive an extremely strong constant-depth circuit lower bound and then magnify it to an $$\textsf{NC}^{1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>NC</mml:mi> <mml:mn>1</mml:mn> </mml:msup> </mml:math> lower bound for an explicit function. To prove this, we show that lower bounds obtained by the approximation method are in many cases localizable in the sense that they imply lower bounds for circuits which are allowed to use arbitrarily powerful oracles with small fan-in.

Ján Pich

Localizability of the approximation method

近似方法的可定位性

Abhranil Chatterjee

Mrinal Kumar

Ben Lee Volk

Determinants vs. Algebraic Branching Programs

确定性因素与代数分支程序

Abstract We introduce the problem of constructing explicit variety evasive subspace families . Given a family $$\mathcal{F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> of subvarieties of a projective or affine space, a collection $$\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> of projective or affine $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspaces is $$(\mathcal{F},\epsilon)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -evasive if for every $$\mathcal{V}\in\mathcal{F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>F</mml:mi> </mml:mrow> </mml:math> , all but at most $$\epsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> -fraction of $$W\in\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>W</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>H</mml:mi> </mml:mrow> </mml:math> intersect every irreducible component of $$\mathcal{V}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>V</mml:mi> </mml:math> with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of low degree in a projective or affine $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester–Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspace families that are evasive for degree- $$d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> varieties in a projective $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. When $$n-k=n^{\Omega(1)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , the lower bound is superpolynomial unless $$d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> is bounded. The proof uses a dimension counting argument on Chow varieties that parametrize projective subvarieties.

Zeyu Guo

Variety Evasive Subspace Families

多样性规避子空间族

Abstract The combinatorial refinement techniques have proven to be an efficient approach to isomorphism testing for particular classes of graphs. If the number of refinement rounds is small, this puts the corresponding isomorphism problem in a low-complexity class. We investigate the round complexity of the two-dimensional Weisfeiler--Leman algorithm on circulant graphs, i.e., on Cayley graphs of the cyclic group $$\mathbb{Z}_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Z</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> , and prove that the number of rounds until stabilization is bounded by $$\mathcal{O}(d(n)\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where $$d(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is the number of divisors of n. As a particular consequence, isomorphism can be tested in NC for connected circulant graphs of order $$p^\ell$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msup> </mml:math> with p an odd prime, $$\ell&gt;3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> and vertex degree $$\Delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> smaller than p. We also show that the color refinement method (also known as the one-dimensional Weisfeiler--Leman algorithm) computes a canonical labeling for every non-trivial circulant graph with a prime number of vertices after individualization of two appropriately chosen vertices. Thus, the canonical labeling problem for this class of graphs has at most the same complexity as color refinement, which results in a time bound of $$\mathcal{O}(\Delta \, n\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Δ</mml:mi> <mml:mspace/> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Moreover, this provides a first example where a sophisticated approach to isomorphism testing put forward by Tinhofer has a real practical meaning.

Abbreviation	Comput. Complex.
Journal Impact	0.59
Quartiles(Global)	MATHEMATICS(Q2)

ISSN	1016-3328, 1420-8954
h-index	41

Publication Information	Publisher: Birkhauser Verlag Basel，Publishing cycle: Quarterly，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 1998，Proportion of original research papers: 100.00%，Self Citation Rate:0.00%， Gold OA Rate: 29.55%
Average review cycle	网友分享经验：>12周，或约稿
Average recruitment ratio	网友分享经验：容易

Computational Complexity

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

PPSZ for General k-SAT and CSP—Making Hertli’s Analysis Simpler and 3-SAT Faster

The electrical resistance of a graph captures its commute and cover times

Correction to: Smooth and Strong PCPs

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

The hardest halfspace

PPSZ for General k-SAT and CSP—Making Hertli’s Analysis Simpler and 3-SAT Faster

Localizability of the approximation method

Determinants vs. Algebraic Branching Programs

Variety Evasive Subspace Families

Combinatorial refinement on circulant graphs