Navid Talebanfard
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Navid Talebanfard has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Ilario Bonacina
Universitat Politècnica de Catalunya Barcelona Spain
2 shared publications Nicola Galesi
Sapienza Università di Roma, Rome, Italy
2 shared publications- Alexander V. Smal
JetBrains Research
1 shared publication Balagopal Komarath
IIT Madras
1 shared publicationBangsheng Tang
1 shared publicationDominik Scheder
1 shared publication
Latest Publications
- 17 August 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (1) , 268-278
On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube
- 17 August 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (1) , 268-278
On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube
- Open Access
Linear Branching Programs and Directional Affine Extractors
A natural model of read-once linear branching programs is a branching program where queries are $\mathbb{F}_2$ linear forms, and along each path, the queries are linearly independent. We consider two restrictions of this model, which we call weakly and strongly read-once, both generalizing standard read-once branching programs and parity decision trees. Our main results are as follows. - Average-case complexity. We define a pseudo-random class of functions which we call directional affine extractors, and show that these functions are hard on average for the strongly read-once model. We then present an explicit construction of such function with good parameters. This strengthens the result of Cohen and Shinkar (ITCS'16) who gave such average-case hardness for parity decision trees. Directional affine extractors are stronger than the more familiar class of affine extractors. Given the significance of these functions, we expect that our new class of functions might be of independent interest. - Proof complexity. We also consider the proof system $\text{Res}[\oplus]$ which is an extension of resolution with linear queries. A refutation of a CNF in this proof system naturally defines a linear branching program solving the corresponding search problem. Conversely, we show that a weakly read-once linear BP solving the search problem can be converted to a $\text{Res}[\oplus]$ refutation with constant blow up.Open AccessLinear Branching Programs and Directional Affine Extractors
A natural model of read-once linear branching programs is a branching program where queries are $\mathbb{F}_2$ linear forms, and along each path, the queries are linearly independent. We consider two restrictions of this model, which we call weakly and strongly read-once, both generalizing standard read-once branching programs and parity decision trees. Our main results are as follows. - Average-case complexity. We define a pseudo-random class of functions which we call directional affine extractors, and show that these functions are hard on average for the strongly read-once model. We then present an explicit construction of such function with good parameters. This strengthens the result of Cohen and Shinkar (ITCS'16) who gave such average-case hardness for parity decision trees. Directional affine extractors are stronger than the more familiar class of affine extractors. Given the significance of these functions, we expect that our new class of functions might be of independent interest. - Proof complexity. We also consider the proof system $\text{Res}[\oplus]$ which is an extension of resolution with linear queries. A refutation of a CNF in this proof system naturally defines a linear branching program solving the corresponding search problem. Conversely, we show that a weakly read-once linear BP solving the search problem can be converted to a $\text{Res}[\oplus]$ refutation with constant blow up. - Open Access
- 13 December 2021
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 17, Is (4)
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and $k\in o(\sqrt{m})$. Furthermore our algorithm solves the corresponding #CSP-SAT and Max-CSP-SAT of these CSPs. We also show that CNF representations of unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation.- 13 December 2021
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 17, Is (4)
Open AccessA Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and $k\in o(\sqrt{m})$. Furthermore our algorithm solves the corresponding #CSP-SAT and Max-CSP-SAT of these CSPs. We also show that CNF representations of unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation. - Open Access
- 4 March 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 12 (2) , 1-22
Cops-Robber Games and the Resolution of Tseitin Formulas
We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed in our game in order to catch a robber in it, we are able to exactly characterize the width, variable space, and depth measures for the resolution of the Tseitin formula corresponding to that graph. We also give an exact game characterization of resolution variable space for any formula. We show that our game can be played in a monotone way. This implies that the associated resolution measures on Tseitin formulas correspond exactly to those under the restriction of Davis-Putnam resolution, implying that this kind of resolution is optimal on Tseitin formulas for all the considered measures. Using our characterizations, we improve the existing complexity bounds for Tseitin formulas showing that resolution width, depth, and variable space coincide up to a logarithmic factor, and that variable space is bounded by the clause space times a logarithmic factor.
- 4 March 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 12 (2) , 1-22
Open AccessCops-Robber Games and the Resolution of Tseitin Formulas
We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed in our game in order to catch a robber in it, we are able to exactly characterize the width, variable space, and depth measures for the resolution of the Tseitin formula corresponding to that graph. We also give an exact game characterization of resolution variable space for any formula. We show that our game can be played in a monotone way. This implies that the associated resolution measures on Tseitin formulas correspond exactly to those under the restriction of Davis-Putnam resolution, implying that this kind of resolution is optimal on Tseitin formulas for all the considered measures. Using our characterizations, we improve the existing complexity bounds for Tseitin formulas showing that resolution width, depth, and variable space coincide up to a logarithmic factor, and that variable space is bounded by the clause space times a logarithmic factor.
- 1 August 2018
- Published by Elsevier in Information Processing Letters
- Vol. 136, 102-104
Prediction from partial information and hindsight, an alternative proof
- 1 August 2018
- Published by Elsevier in Information Processing Letters
- Vol. 136, 102-104
Prediction from partial information and hindsight, an alternative proof
- 26 June 2018
- Published by Springer Nature
- p. 311-326
Cops-Robber Games and the Resolution of Tseitin Formulas
- 26 June 2018
- Published by Springer Nature
- p. 311-326
Cops-Robber Games and the Resolution of Tseitin Formulas
- 19 October 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (1) , 29-41
Strong ETH and Resolution via Games and the Multiplicity of Strategies
- 19 October 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (1) , 29-41
Strong ETH and Resolution via Games and the Multiplicity of Strategies
- 1 February 2016
- Published by Elsevier in Information Processing Letters
- Vol. 116 (2) , 120-124
Improving resolution width lower bounds for k -CNFs with applications to the Strong Exponential Time Hypothesis
- 1 February 2016
- Published by Elsevier in Information Processing Letters
- Vol. 116 (2) , 120-124
Improving resolution width lower bounds for k -CNFs with applications to the Strong Exponential Time Hypothesis
- 1 February 2016
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 200, 1-4
On the structure and the number of prime implicants of 2-s- 1 February 2016
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 200, 1-4
On the structure and the number of prime implicants of 2-s- Open Access
On the Structure and the Number of Prime Implicants of 2-CNFs
Let $m(n, k)$ be the maximum number of prime implicants that any $k$-CNF on n variables can have. We show that $3^{n/3} \le m(n,2) \le (1+o(1))3^{n/3}$.Open AccessOn the Structure and the Number of Prime Implicants of 2-CNFs
Let $m(n, k)$ be the maximum number of prime implicants that any $k$-CNF on n variables can have. We show that $3^{n/3} \le m(n,2) \le (1+o(1))3^{n/3}$.