Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR24-121 | 16th July 2024
Nader Bshouty

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

Revisions: 1

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 >>>

TR24-120 | 15th July 2024
Halley Goldberg, Valentine Kabanets

Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

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 >>>

TR24-119 | 14th July 2024
Vishwas Bhargava, Anamay Tengse

Explicit Commutative ROABPs from Partial Derivatives

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 next

ISSN 1433-8092 | Imprint