← 研踪 PaperTrailarXiv:2611.11966 · v1
On Non-Deterministic Representation of Boolean Functions
首次提交 2026-11-09 14:44
版本更新 2026-11-09 14:44
雷达观测 2026-11-10 13:18
摘要
We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial is said to be a non-deterministic polynomial for a Boolean function if for all , iff . The non-deterministic degree of , denoted , is the minimal degree of a non-deterministic polynomial for . In this work, we show the following main results: - Almost all Boolean functions on variables have non-deterministic degree at most . This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.
作者备注:15 pages, to appear in FSTTCS 2026
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 14:44 · 最新观测版本
On Non-Deterministic Representation of Boolean Functions
We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial is said to be a non-deterministic polynomial for a Boolean function if for all , iff . The non-deterministic degree of , denoted , is the minimal degree of a non-deterministic polynomial for . In this work, we show the following main results: - Almost all Boolean functions on variables have non-deterministic degree at most . This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.
查看此版本解读 →查看此版本原文 ↗