A hitting-set generator (HSG) is a polynomial map ${{\mathsf{Gen}}}:{\mathbb{F}}^k \to {\mathbb{F}}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ {{\mathsf{Gen}}}$ is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following result over any field ${\mathbb{F}}$ of characteristic zero: Let $k\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. Suppose ${\left\{ {P_d} \right\}}_{d\in {\mathbb{N}}}$ is an explicit family of $k$-variate polynomials such that $\deg P_d = d$ and $P_d$ requires algebraic circuits of size $d^\delta$. Then, there are explicit hitting sets of polynomial size for the class ${\mathsf{VP}}$. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps [N. Nisan and A. Wigderson, J. Comput. System Sci., 49 (1994), pp. 149--167; V. Kabanets and R. Impagliazzo, Comput. Complexity, 13 (2004), pp. 1--46; M. Agrawal, S. Ghosh, and N.Saxena, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8107--8118; M. Kumar, R. Saptharishi, and A. Tengse, Proceedings of the \textup30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 639--646], our construction is purely algebraic and does not rely on the notion of combinatorial designs. As a direct consequence, we show that even saving a single point from the “trivial” explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s^\delta$ circuits. Then there is an explicit hitting set of size ${\operatorname{poly}}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $\tau$-conjecture of Shub and Smale [M. Shub and S. Smale, Duke Math. J., 81 (1995), pp. 47--54; S. Smale, Math. Intelligencer, 20 (1998), pp. 7--15] is true.

The goal in reconfiguration problems is to compute a gradual transformation between two feasible solutions of a problem such that all intermediate solutions are also feasible. In the Matching Reconfiguration Problem (MRP), proposed in a pioneering work by Ito et al. from 2008, we are given a graph G and two matchings M and M', and we are asked whether there is a sequence of matchings in G starting with M and ending at M', each resulting from the previous one by either adding or deleting a single edge in G, without ever going through a matching of size < min{|M|,|M'|}-1. Ito et al. gave a polynomial time algorithm for the problem, which uses the Edmonds-Gallai decomposition. In this paper we introduce a natural generalization of the MRP that depends on an integer parameter Δ ≥ 1: here we are allowed to make Δ changes to the current solution rather than 1 at each step of the {transformation procedure}. There is always a valid sequence of matchings transforming M to M' if Δ is sufficiently large, and naturally we would like to minimize Δ. We first devise an optimal transformation procedure for unweighted matching with Δ = 3, and then extend it to weighted matchings to achieve asymptotically optimal guarantees. The running time of these procedures is linear. We further demonstrate the applicability of this generalized problem to dynamic graph matchings. In this area, the number of changes to the maintained matching per update step (the recourse bound) is an important quality measure. Nevertheless, the worst-case recourse bounds of almost all known dynamic matching algorithms are prohibitively large, much larger than the corresponding update times. We fill in this gap via a surprisingly simple black-box reduction: Any dynamic algorithm for maintaining a β-approximate maximum cardinality matching with update time T, for any β ≥ 1, T and ε > 0, can be transformed into an algorithm for maintaining a (β(1 +ε))-approximate maximum cardinality matching with update time T + O(1/ε) and worst-case recourse bound O(1/ε). This result generalizes for approximate maximum weight matching, where the update time and worst-case recourse bound grow from T + O(1/ε) and O(1/ε) to T + O(ψ/ε) and O(ψ/ε), respectively; ψ is the graph aspect-ratio. We complement this positive result by showing that, for β = 1+ε, the worst-case recourse bound of any algorithm produced by our reduction is optimal. As a corollary, several key dynamic approximate matching algorithms - with poor worst-case recourse bounds - are strengthened to achieve near-optimal worst-case recourse bounds with no loss in update time.

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold (Computational Complexity, 2013). In this paper, we show that improved bounds for DNF compression imply improved bounds for the sunflower conjecture, which is the reverse direction of the DNF compression result. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.

A hitting-set generator (HSG) is a polynomial map Gen:Fk→ Fnsuch that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q o Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field F: Suppose P(z1,..., zk) is an explicit k-variate degree d polynomial that is not in the border of circuits of size s. Then, there is an explicit hitting-set generator Gen(P): F2k→ Fnsuch that every non-zero n-variate degree D polynomial Q(x) in the border of size s' circuits satisfies Q ≠ 0 ⇒ Q o Gen(P) ≠ 0 provided n10kd Ds'0 be a constant and k be a large enough constant. Suppose, for every s ≥ k, there is an explicit hitting set of size sk-δfor all degree s polynomials in the border of k-variate size s algebraic circuits. Then, there is an explicit hitting set of size poly(s) for the border s-variate algebraic circuits of size s and degree s. Unlike the prior constructions of such maps (e.g.[NW94], [KI04], [AGS19], [KST19]), our construction is purely algebraic and does not rely on the notion of combinatorial designs.

In this paper, we study the question of hardness-randomness tradeoffs for bounded depth arithmetic circuits. We show that if there is a family of explicit polynomials {f_n}, where f_n is of degree O(log^2n/log^2 log n) in n variables such that f_n cannot be computed by a depth Delta arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta-5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth Delta-5 circuits of bounded individual degree. Thus, we remove the "bounded individual degree" condition in the work of Dvir et al. at the cost of strengthening the hardness assumption to hold for polynomials of low degree. The key technical ingredient of our proof is the following property of roots of polynomials computable by a bounded depth arithmetic circuit : if f(x_1, x_2, ..., x_n) and P(x_1, x_2, ..., x_n, y) are polynomials of degree d and r respectively, such that P can be computed by a circuit of size s and depth Delta and P(x_1, x_2, ..., x_n, f) equiv 0, then, f can be computed by a circuit of size poly(n, s, r, d^{O(sqrt{d})}) and depth Delta + 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth Delta + 3 and size poly(n, s, r, d^{t}), where t is the degree of P in y. Thus, the size upper bound in the work of Dvir et al. is non-trivial when t is small but d could be large, whereas our size upper bound is non-trivial when d is small, but t could be large.

We study a wide spectrum of incidence problems involving points and curves or points and surfaces in ℝ3. The current (and in fact the only viable) approach to such problems, pioneered by Guth and Katz [35, 36], requires a variety of tools from algebraic geometry, most notably (i) the polynomial partitioning technique, and (ii) the study of algebraic surfaces that are ruled by lines or, in more recent studies [37], by algebraic curves of some constant degree. By exploiting and refining these tools, we obtain new and improved bounds for numerous incidence problems in ℝ3. In broad terms, we consider two kinds of problems, those involving points and constant-degree algebraic curves, and those involving points and constant-degree algebraic surfaces. In some variants we assume that the points lie on some fixed constant-degree algebraic variety, and in others we consider arbitrary sets of points in 3-space. The case of points and curves has been considered in several previous studies, starting with Guth and Katz's work on points and lines [36]. Our results, which are based on a recent work of Guth and Zahl [37] concerning surfaces that are doubly ruled by curves, provide a grand generalization of all previous results. We reconstruct the bound for points and lines, and improve, in certain significant ways, recent bounds involving points and circles (in [50]) and points and arbitrary constant-degree algebraic curves (in [49]). While in these latter instances the bounds are not known (and are strongly suspected not) to be tight, our bounds are, in a certain sense, the best that can be obtained with this approach, given the current state of knowledge. In the case of points and surfaces, the incidence graph between them can contain large complete bipartite graphs, each involving points on some curve and surfaces containing this curve (unlike earlier studies, we do not rule out this possibility, which makes our approach more general). Our bounds estimate the total size of the vertex sets in such a complete bipartite graph decomposition of the incidence graph. In favorable cases, our bounds translate into actual incidence bounds. Overall, here too our results can be regarded as providing a “grand generalization” of most of the previous studies of (special instances of) this problem. As applications of our point-surface incidence bounds, we consider the problems of distinct and repeated distances determined by a set of n points in ℝ3, two of the most celebrated open problems in combinatorial geometry. We obtain new and improved bounds for two special cases, one in which the points lie on some algebraic variety of constant degree, and one involving distances between pairs in P1 × P2, where Pi is contained in a variety and P2 is arbitrary.

We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^3, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between m and n). This bound, originally obtained by Guth and Katz as a major step in their solution of Erdos's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.

We show that the number of incidences between m distinct points and n distinct lines in R4is O(2c√log m(m2/5n4/5+ m) + m1/2n1/2q1/4+ m2/3n1/3s1/3+ n), for a suitable absolute constant c, provided that no 2-plane contains more than s input lines, and no hyperplane or quadric contains more than q lines. The bound holds without the extra factor 2c√log mwhen m ≤ n6/7or m ≥ n5/3. Except for this possible factor, the bound is tight in the worst case. The context of this work is incidence geometry, a topic that has been widely studied for more than three decades, with strong connections to a variety of topics, from range searching in computational geometry to the Kakeya problem in harmonic analysis and geometric measure theory. The area has picked up considerable momentum in the past seven years, following the seminal works of Guth and Katz [12, 13], where the later work solves the point-line incidence problem in three dimensions, using new tools and techniques from algebraic geometry. This work extends their result to four dimensions. In doing so, it had to overcome many new technical hurdles that arise from the higher-dimensional context, by developing and adapting more advanced tools from algebraic geometry.

We show that the number of incidences between m distinct points and n distinct lines in R4 is at most

The Tower of Hanoi problem is generalized by placing pegs on the vertices of a given directed graph G with two distinguished vertices, S and D , and allowing moves only along arcs of this graph. An optimal solution for such a graph G is an algorithm that completes the task of moving a tower of any given number of disks from S to D in a minimal number of disk moves. In this article we present an algorithm which solves the problem for two infinite families of graphs, and prove its optimality. To the best of our knowledge, this is the first optimality proof for an infinite family of graphs. Furthermore, we present a unified algorithm that solves the problem for a wider family of graphs and conjecture its optimality.