Abstract. Let us consider a collection [Formula: see text] of codewords of length [Formula: see text] over an alphabet of size [Formula: see text]. Let [Formula: see text] be nonnegative integers. What is the maximum of [Formula: see text] subject to the condition that any two codewords should have at least [Formula: see text] positions where both have letter [Formula: see text] ([Formula: see text])? In the case [Formula: see text] it is a longstanding open question. Quite surprisingly we obtain an almost complete answer for [Formula: see text]. The main tool is a correlation inequality.

Let n,k,ℓ,t be positive integers with k≥ℓ≥t+2 and let X=X1⊎X2⊎⋯⊎Xk, |Xi|=n. A family F of ℓ-subsets of X is called a separated family if |F∩Xi|≤1 for all F∈F and i=1,2,…,k. A separated family F is called non-trivial t-intersecting if |F∩F′|≥t for all F,F′∈F and |∩{F:F∈F}| (t+1)(ℓ−t−1)2(k−t−1)+1.

Abstract. We consider the minimum number of lines [Formula: see text] and [Formula: see text] needed to intersect or pierce, respectively, all the cells of the [Formula: see text] chessboard. Determining these values can also be interpreted as a strengthening of the classical plank problem for integer points. Using the symmetric plank theorem of K. Ball, we prove that [Formula: see text] for each [Formula: see text]. Studying the piercing problem, we show that [Formula: see text] for [Formula: see text], where the upper bound is conjectured to be sharp. The lower bound is proven by using the linear programming method, whose limitations are also demonstrated.

We introduce the following variant of the VC-dimension. Given S ⊆ {0,1}ⁿ and a positive integer d, we define 𝕌_d(S) to be the size of the largest subset I ⊆ [n] such that the projection of S on every subset of I of size d is the d-dimensional cube. We show that determining the largest cardinality of a set with a given 𝕌_d dimension is equivalent to a Turán-type problem related to the total number of cliques in a d-uniform hypergraph. This allows us to beat the Sauer-Shelah lemma for this notion of dimension. We use this to obtain several results on Σ₃^k-circuits, i.e., depth-3 circuits with top gate OR and bottom fan-in at most k: - Tight relationship between the number of satisfying assignments of a 2-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. '00). - Improved Σ₃³-circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement. - We make progress towards settling the Σ₃² complexity of the inner product function and all degree-2 polynomials over 𝔽₂ in general. The question of determining the Σ₃³ complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21).

In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\cal F$ covering an $n$-element ground set which satisfies the following condition: for any two disjoint members $A, B\in\cal F$, there exist $a\in A$ and $b\in B$ such that either $B\cup\{a\}\in\cal F$ and $A\cup\{b\}\setminus\{a\}\in\cal F$, or $A\cup\{b\}\in\cal F$ and $B\cup\{a\}\setminus\{b\}\in\cal F$. Denoting by $f(n)$ the smallest cardinality of such a family $\cal F$, they proved that $f(n)<2^{O(\sqrt{n}\log n)}$, and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito, Avvakumov, and Karasev is not far from optimal; we show that $2^{(1.42+o(1))\sqrt{n}}\le f(n)\le 2^{(1+o(1))\sqrt{2n\log n}}$. We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members $A, B\in\cal F$ with $|A|>|B|$, there exists $a\in A$ such that $B\cup\{a\}\in\cal F$. In this case, we prove that the size of the smallest $\cal F$ satisfying this stronger condition lies between $2^{\Omega(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$.

A family $\mathcal{F}$ of subsets of the n-set [n] is a k-antichain if it contains no $F_0 , \cdots , F_k $ satisfying $F_0 \subset \cdots \subset F_k $. Extending theorems of Sperner, Erdös, Bollobás, and Purdy the maximum size of k-antichains is determined under the additional assumptions that (i) $\mathcal{F}$ is self-complementary ($F \in \mathcal{F}$ implies $( [ n ] - F ) \in \mathcal{F}$) (ii) complement-free ($F \in \mathcal{F}$ implies $( [ n ] - F ) \notin \mathcal{F}$). These results are corollaries of more general results on convex hulls of f-vectors. An easy proof of a theorem of Alon and a two-family version of it are also provided.

We take a complexity theoretic view of A. C. Yao's theory of communication complexity. A rich structure of natural complexity classes is introduced. Besides providing a more structured approach to the complexity of a variety of concrete problems of interest to VLSI, the main objective is to exploit the analogy between Turing machine (TM) and communication complexity (CC) classes. The latter provide a more amicable environment for the study of questions analogous to the most notorious problems in TM complexity. Implicitly, CC classes corresponding to P, NP, coNP, BPP and PP have previously been considered. Surprisingly, pcc = Npcc ∩ coNPcc is known [AUY]. We develop the definitions of PSPACEcc and of the polynomial time hierarchy in CC. Notions of reducibility are introduced and a natural complete member in each class is found. BPPcc ⊆ Σ2cc ∩ Π2cc [Si2] remains valid. We solve the question that BPPcc ⊉ NPcc by proving an Ω(√n) lower bound for the bounded-error complexity of the coNPcc- complete problem "disjointness". Similar lower bounds follow for essentially any nontrivial monotone graph property. Another consequence is that the deterministically exponentially hard "equality" relation is not NPcc-hard with respect to oracle-protocol reductions. We prove that the distributional complexity of the disjointness problem is O(√n log n) under any product measure on {0, 1}n × {0, 1}n. This points to the difficulty of improving the Ω(√n) lower bound for the B2PP complexity of "disjointness". The variety of counting and probabilistic classes appears to be greater than in the Turing machine versions. Many of the simplest graph problems (undirected reachability, planarity, bipartiteness, 2-CNF-satisfiability) turn out to be PSPACEcc-hard. The main open problem remains the separation of the hierarchy, more specifically, the conjecture that Σ2cc ≠ Π2cc. Another major problem is to show that PSPACEcc and the probabilistic class UPPcc are not comparable.

Let d = d(n) be the minimum d such that for every sequence of n subsets F1, F2, . . . , Fn of {1, 2, . . . , n} there exist n points P1, P2, . . . , Pn and n hyperplanes H1, H2 .... , Hn in Rd such that Pj lies in the positive side of Hi iff j ∈ Fi. Then n/32 ≤ d(n) ≤ (1/2 + 0(1)) · n. This implies that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. The proof of (1) combines some known geometric facts with certain probabilistic arguments and a theorem of Milnor from real algebraic geometry.