Next

__
TR24-121
| 16th July 2024
__

Nader Bshouty#### Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Revisions: 1

__
TR24-120
| 15th July 2024
__

Halley Goldberg, Valentine Kabanets#### Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

__
TR24-119
| 14th July 2024
__

Vishwas Bhargava, Anamay Tengse#### Explicit Commutative ROABPs from Partial Derivatives

Next

Nader Bshouty

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>

Halley Goldberg, Valentine Kabanets

A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, ... more >>>

Vishwas Bhargava, Anamay Tengse

The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize ... more >>>

Next