The problem of learning $t$-term DNF formulas (for $t = O(1)$) has been
studied extensively in the PAC model since its introduction by Valiant (STOC
1984). A $t$-term DNF can be efficiently learnt using a $t$-term DNF only if $t
= 1$ i.e., when it is an AND, while even weakly learning a $2$-term DNF using a
constant term DNF was shown to be NP-hard by Khot and Saket (FOCS 2008). On the
other hand, Feldman et al. (FOCS 2009) showed the hardness of weakly learning a
noisy AND using a halfspace -- the latter being a generalization of an AND,
while Khot and Saket (STOC 2008) showed that an intersection of two halfspaces
is hard to weakly learn using any function of constantly many halfspaces. The
question of whether a $2$-term DNF is efficiently learnable using $2$ or
constantly many halfspaces remained open.
In this work we answer this question in the negative by showing the hardness
of weakly learning a $2$-term DNF as well as a noisy AND using any function of
a constant number of halfspaces. In particular we prove the following....

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

For most relevant computation, the energy and time needed for data movement
dominates that for performing arithmetic operations on all computing systems
today. Hence it is of critical importance to understand the minimal total data
movement achievable during the execution of an algorithm. The achieved total
data movement for different schedules of an algorithm can vary widely depending
on how efficiently the cache is used, e.g., untiled versus effectively tiled
matrix-matrix multiplication. A significant current challenge is that no
existing tool is able to meaningfully quantify the potential reduction to the
data movement of a computation that can be achieved by more effective use of
the cache through operation rescheduling. Asymptotic parametric expressions of
data movement lower bounds have previously been manually derived for a limited
number of algorithms, often without scaling constants. In this paper, we
present the first compile-time approach for deriving non-asymptotic parametric
expressions of data movement lower bounds...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 0

Unqiue Words: 0

We introduce the binary value principle which is a simple subset-sum instance
expressing that a natural number written in binary cannot be negative, relating
it to central problems in proof and algebraic complexity. We prove conditional
superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of
this instance, based on a well-known hypothesis by Shub and Smale about the
hardness of computing factorials, where IPS is the strong algebraic proof
system introduced by Grochow and Pitassi (2018). Conversely, we show that short
IPS refutations of this instance bridge the gap between sufficiently strong
algebraic and semi-algebraic proof systems. Our results extend to full-fledged
IPS the paradigm introduced in Forbes et al. (2016), whereby lower bounds
against subsystems of IPS were obtained using restricted algebraic circuit
lower bounds, and demonstrate that the binary value principle captures the
advantage of semi-algebraic over algebraic reasoning, for sufficiently strong
systems. Specifically, we show the...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 223,555 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible