Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Kayal, Chandrima"'
Let $\mathbb{F}$ be a field, and consider the hypercube $\{ 0, 1 \}^{n}$ in $\mathbb{F}^{n}$. Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a polynomial $P ( X_{1}, \dots, X_{n} ) \in \mathbb{F}[ X_{1}, \dots, X_{
Externí odkaz:
http://arxiv.org/abs/2409.10573
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types
Externí odkaz:
http://arxiv.org/abs/2407.08385
In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to log n factor, for any Boolean function composed with AND function as the inner gadget. One of the main tools in this res
Externí odkaz:
http://arxiv.org/abs/2406.07859
Two Boolean functions f, g : F_2^{n} \to {-1, 1} are called linearly isomorphic if there exists an invertible matrix M \in F_2^{n\times n} such that f\circ M = g. Testing linear isomorphism is a generalization of, now classical in the context of prop
Externí odkaz:
http://arxiv.org/abs/2308.02662
Alon and F\"uredi (European J. Combin. 1993) gave a tight bound for the following hyperplane covering problem: find the minimum number of hyperplanes required to cover all points of the n-dimensional hypercube {0,1}^n except the origin. Their proof i
Externí odkaz:
http://arxiv.org/abs/2307.16881
Autor:
Chakraborty, Sourav, Kayal, Chandrima, Mittal, Rajat, Paraashar, Manaswi, Sanyal, Swagato, Saurabh, Nitin
For any Boolean functions $f$ and $g$, the question whether $R(f\circ g) = \tilde{\Theta}(R(f)R(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whethe
Externí odkaz:
http://arxiv.org/abs/2307.03900
Given a hypercube $\mathcal{Q}^{n} := \{0,1\}^{n}$ in $\mathbb{R}^{n}$ and $k \in \{0, \dots, n\}$, the $k$-th layer $\mathcal{Q}^{n}_{k}$ of $\mathcal{Q}^{n}$ denotes the set of all points in $\mathcal{Q}^{n}$ whose coordinates contain exactly $k$ m
Externí odkaz:
http://arxiv.org/abs/2207.13752
The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of $S_n$, is an important class of functio
Externí odkaz:
http://arxiv.org/abs/2103.12355
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Chakraborty, S, Kayal, C & Paraashar, M 2022, Separations Between Combinatorial Measures for Transitive Functions . in M Bojanczyk, E Merelli & D P Woodruff (eds), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 ., 36, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022, Paris, France, 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.36
The role of symmetry in Boolean functions f:{0, 1}ⁿ → {0, 1} has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of 𝖲_n, is an important class of functions
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9f890caf4aa8cb84abd45de58ded9034
https://pure.au.dk/portal/da/publications/separations-between-combinatorial-measures-for-transitive-functions(6cef3d09-08bb-4c6f-92bf-dc21b632f9a5).html
https://pure.au.dk/portal/da/publications/separations-between-combinatorial-measures-for-transitive-functions(6cef3d09-08bb-4c6f-92bf-dc21b632f9a5).html