10 Search Results for "Tavenas, Sébastien"

Document
DOI: 10.4230/LIPIcs.CCC.2023.28
Towards Optimal Depth-Reductions for Algebraic Formulas

Authors: Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula. Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth O(log d) and size poly(s). Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas. This improves on previous results in the regime when d is small (i.e., d = s^o(1)). In particular, for the setting of d = O(log s), along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas. This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting. We also show that these results cannot be improved in the monotone setting, even for commutative formulas.
Cite as

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas. Towards Optimal Depth-Reductions for Algebraic Formulas. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 28:1-28:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.CCC.2023.28,
  author =	{Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{Towards Optimal Depth-Reductions for Algebraic Formulas}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.28},
  URN =		{urn:nbn:de:0030-drops-182986},
  doi =		{10.4230/LIPIcs.CCC.2023.28},
  annote =	{Keywords: Algebraic formulas, depth-reduction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.9
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families

Authors: Antoine Amarilli and Mikaël Monet

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We consider a weighted counting problem on matchings, denoted PrMatching(𝒢), on an arbitrary fixed graph family 𝒢. The input consists of a graph G ∈ 𝒢 and of rational probabilities of existence on every edge of G, assuming independence. The output is the probability of obtaining a matching of G in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if 𝒢 has bounded treewidth, then PrMatching(𝒢) can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families 𝒢 satisfying the following treewidth-constructibility requirement: given an integer k in unary, we can construct in polynomial time a graph G ∈ 𝒢 with treewidth at least k. Our hardness result is then the following: for any treewidth-constructible graph family 𝒢, the problem PrMatching(𝒢) is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in [Amarilli et al., 2016]. We also obtain a similar lower bound for the weighted counting of edge covers.
Cite as

Antoine Amarilli and Mikaël Monet. Weighted Counting of Matchings in Unbounded-Treewidth Graph Families. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 9:1-9:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.MFCS.2022.9,
  author =	{Amarilli, Antoine and Monet, Mika\"{e}l},
  title =	{{Weighted Counting of Matchings in Unbounded-Treewidth Graph Families}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.9},
  URN =		{urn:nbn:de:0030-drops-168078},
  doi =		{10.4230/LIPIcs.MFCS.2022.9},
  annote =	{Keywords: Treewidth, counting complexity, matchings, Fibonacci sequence}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.32
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

Authors: Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits. More specifically, our previous work applied the well-known partial derivative method in a new setting, that of lopsided set-multilinear polynomials. A set-multilinear polynomial P ∈ 𝔽[X_1,…,X_d] (for disjoint sets of variables X_1,…,X_d) is a linear combination of monomials, each of which contains one variable from X_1,…,X_d. A lopsided space of set-multilinear polynomials is one where the sets X_1,…,X_d are allowed to have different sizes (we use the adjective "lopsided" to stress this feature). By choosing a suitable lopsided space of polynomials, and using a suitable version of the partial-derivative method for proving lower bounds, we were able to prove constant-depth superpolynomial set-multilinear formula lower bounds even for very low-degree polynomials (as long as d is a growing function of the number of variables N). This in turn implied lower bounds against general formulas of constant-depth. A priori, there is nothing stopping these techniques from giving us lower bounds against algebraic formulas of any depth. We investigate the extent to which this lower bound can extend to greater depths. We prove the following results. 1) We observe that our choice of the lopsided space and the kind of partial-derivative method used can be modeled as the choice of a multiset W ⊆ [-1,1] of size d. Our first result completely characterizes, for any product-depth Δ, the best lower bound we can prove for set-multilinear formulas of product-depth Δ in terms of some combinatorial properties of W, that we call the depth-Δ tree bias of W. 2) We show that the maximum depth-3 tree bias, over multisets W of size d, is Θ(d^{1/4}). This shows a stronger formula lower bound of N^{Ω(d^{1/4})} for set-multilinear formulas of product-depth 3, and also puts a non-trivial constraint on the best lower bounds we can hope to prove at this depth in this framework (a priori, we could have hoped to prove a lower bound of N^{Ω(Δ d^{1/Δ})} at product-depth Δ). 3) Finally, we show that for small Δ, our proof technique cannot hope to prove lower bounds of the form N^{Ω(d^{1/poly(Δ)})}. This seems to strongly hint that new ideas will be required to prove lower bounds for formulas of unbounded depth.
Cite as

Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 32:1-32:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32,
  author =	{Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{32:1--32:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.32},
  URN =		{urn:nbn:de:0030-drops-165942},
  doi =		{10.4230/LIPIcs.CCC.2022.32},
  annote =	{Keywords: Partial Derivative Method, Barriers to Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.15
Nonnegative Rank Measures and Monotone Algebraic Branching Programs

Authors: Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Inspired by Nisan’s characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.
Cite as

Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas. Nonnegative Rank Measures and Monotone Algebraic Branching Programs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 15:1-15:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.FSTTCS.2019.15,
  author =	{Fournier, Herv\'{e} and Malod, Guillaume and Szusterman, Maud and Tavenas, S\'{e}bastien},
  title =	{{Nonnegative Rank Measures and Monotone Algebraic Branching Programs}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.15},
  URN =		{urn:nbn:de:0030-drops-115774},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.15},
  annote =	{Keywords: Elementary symmetric polynomials, lower bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.78
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

Authors: Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 syntactically multilinear (Sigma Pi Sigma Pi) circuit of size at most exp ({O (sqrt{n log n})}). For degree d = omega(n/log n), this improves upon the upper bound of exp ({O(sqrt{d}log n)}) obtained by Tavenas [Sébastien Tavenas, 2015] for general circuits, and is known to be asymptotically optimal in the exponent when d < n^{epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp ({Omega (sqrt{n log n})}) proved by Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009], and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth Delta of size at most exp inparen{O inparen{Delta * (n/log n)^{1/Delta} * log n}}. It follows from the lower bounds of Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009] that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to o inparen{inparen{n/log n}^{1/Delta}* log n}.
Cite as

Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78,
  author =	{Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad},
  title =	{{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{78:1--78:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.78},
  URN =		{urn:nbn:de:0030-drops-106548},
  doi =		{10.4230/LIPIcs.ICALP.2019.78},
  annote =	{Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.21
Reconstruction of Full Rank Algebraic Branching Programs

Authors: Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
An algebraic branching program (ABP) A can be modelled as a product expression X_1 X_2 ... X_d, where X_1 and X_d are 1 x w and w x 1 matrices respectively, and every other X_k is a w x w matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 x 1 matrix obtained from the product X_1 X_2 ... X_d. We say A is a full rank ABP if the w^2(d-2) + 2w linear forms occurring in the matrices X_1, X_2, ... , X_d are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs 'no full rank ABP exists' (with high probability). The running time of the algorithm is polynomial in m and b, where b is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k-1} x w_k matrix (with w_0 = w_d = 1), and v = (w_1, ..., w_{d-1}) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{v,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in N^{d-1}. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM_{v,d} and the 'layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{v,d} and show that IMM_{v,d} is characterized by its group of symmetries.
Cite as

Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 21:1-21:61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2017.21,
  author =	{Kayal, Neeraj and Nair, Vineet and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{Reconstruction of Full Rank Algebraic Branching Programs}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{21:1--21:61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.21},
  URN =		{urn:nbn:de:0030-drops-75318},
  doi =		{10.4230/LIPIcs.CCC.2017.21},
  annote =	{Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.15
On the Sensitivity Conjecture for Disjunctive Normal Forms

Authors: Karthik C. S. and Sébastien Tavenas

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
The sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function f, the maximum sensitivity s(f), is polynomially related to its block sensitivity bs(f), and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function f admitting the Normalized Block property, bs(f) <= 4 * s(f)^2. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property. Recently, Gopalan et al. [ITCS'16] showed that every Boolean function f is uniquely specified by its values on a Hamming ball of radius at most 2 * s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.
Cite as

Karthik C. S. and Sébastien Tavenas. On the Sensitivity Conjecture for Disjunctive Normal Forms. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 15:1-15:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{s._et_al:LIPIcs.FSTTCS.2016.15,
  author =	{S., Karthik C. and Tavenas, S\'{e}bastien},
  title =	{{On the Sensitivity Conjecture for Disjunctive Normal Forms}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.15},
  URN =		{urn:nbn:de:0030-drops-68504},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.15},
  annote =	{Keywords: Boolean function, Sensitivity, Block sensitivity, DNF}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.33
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Authors: Neeraj Kayal, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
Cite as

Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 33:1-33:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.ICALP.2016.33,
  author =	{Kayal, Neeraj and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.33},
  URN =		{urn:nbn:de:0030-drops-63126},
  doi =		{10.4230/LIPIcs.ICALP.2016.33},
  annote =	{Keywords: arithmetic circuits, depth-3 circuits, shifted partials}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.16
On the Sensitivity Conjecture for Read-k Formulas

Authors: Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over R, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the "missing link". Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and functions describing graph properties. In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.
Cite as

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.MFCS.2016.16,
  author =	{Bafna, Mitali and Lokam, Satyanarayana V. and Tavenas, S\'{e}bastien and Velingker, Ameya},
  title =	{{On the Sensitivity Conjecture for Read-k Formulas}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16},
  URN =		{urn:nbn:de:0030-drops-64317},
  doi =		{10.4230/LIPIcs.MFCS.2016.16},
  annote =	{Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.642
Building Efficient and Compact Data Structures for Simplicial Complexes

Authors: Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.
Cite as

Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas. Building Efficient and Compact Data Structures for Simplicial Complexes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 642-657, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SOCG.2015.642,
  author =	{Boissonnat, Jean-Daniel and S., Karthik C. and Tavenas, S\'{e}bastien},
  title =	{{Building Efficient and Compact Data Structures for Simplicial Complexes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{642--657},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.642},
  URN =		{urn:nbn:de:0030-drops-50981},
  doi =		{10.4230/LIPIcs.SOCG.2015.642},
  annote =	{Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard}
}
  • Refine by Author
  • 8 Tavenas, Sébastien
  • 2 Fournier, Hervé
  • 2 Kayal, Neeraj
  • 2 Limaye, Nutan
  • 2 Malod, Guillaume
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Algebraic complexity theory
  • 1 Mathematics of computing → Matchings and factors
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 2 arithmetic circuits
  • 2 lower bounds
  • 1 Algebraic formulas
  • 1 Automaton
  • 1 Barriers to Lower Bounds
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2016
  • 2 2019
  • 2 2022
  • 1 2015
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact