Found 2 Possible Name Variants:

Document

Complete Volume

**Published in:** LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

LIPIcs, Volume 93, FSTTCS'17, Complete Volume

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{lokam_et_al:LIPIcs.FSTTCS.2017, title = {{LIPIcs, Volume 93, FSTTCS'17, Complete Volume}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017}, URN = {urn:nbn:de:0030-drops-85391}, doi = {10.4230/LIPIcs.FSTTCS.2017}, annote = {Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Logics and Meanings of Programs} }

Document

Front Matter

**Published in:** LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Front Matter, Table of Contents, Preface, Conference Organization

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lokam_et_al:LIPIcs.FSTTCS.2017.0, author = {Lokam, Satya and Ramanujam, R.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.0}, URN = {urn:nbn:de:0030-drops-83720}, doi = {10.4230/LIPIcs.FSTTCS.2017.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers} }

Document

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

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.

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

**Published in:** LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

The rigidity of a matrix $A$ for target rank $r$ is the minimum number
of entries of $A$ that must be changed to ensure that the rank of
the altered matrix is at most $r$. Since its introduction by Valiant
\cite{Val77}, rigidity and similar rank-robustness functions of
matrices have found numerous applications in circuit complexity,
communication complexity, and learning complexity. Almost all $\nbyn$
matrices over an infinite field have a rigidity of $(n-r)^2$. It is a
long-standing open question to construct infinite families of
\emph{explicit} matrices even with superlinear rigidity when $r=\Omega(n)$.
In this paper, we construct an infinite family of complex matrices
with the largest possible, i.e., $(n-r)^2$, rigidity. The entries of
an $\nbyn$ matrix in this family are distinct primitive roots of unity
of orders roughly \SL{$\exp(n^4 \log n)$}. To the best of our knowledge, this is
the first family of concrete (but not entirely explicit) matrices
having maximal rigidity and a succinct algebraic description.
Our construction is based on elimination theory of polynomial
ideals. In particular, we use results on the existence of polynomials
in elimination ideals with effective degree upper bounds (effective
Nullstellensatz). Using elementary algebraic geometry, we prove that
the dimension of the affine variety of matrices of rigidity at
most $k$ is exactly $n^2 - (n-r)^2 +k$. Finally, we use elimination theory to
examine whether the rigidity function is semicontinuous.

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and Jayalal Sarma M. N.. Using Elimination Theory to construct Rigid Matrices. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 299-310, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2009.2327, author = {Kumar, Abhinav and Lokam, Satyanarayana V. and Patankar, Vijay M. and Sarma M. N., Jayalal}, title = {{Using Elimination Theory to construct Rigid Matrices}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {299--310}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2327}, URN = {urn:nbn:de:0030-drops-23278}, doi = {10.4230/LIPIcs.FSTTCS.2009.2327}, annote = {Keywords: Matrix Rigidity, Lower Bounds, Circuit Complexity} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail