Michael Schmitt

In a great variety of neuron models neural inputs are

combined using the summing operation. We introduce the concept of

multiplicative neural networks which contain units that multiply

their inputs instead of summing them and, thus, allow inputs to

interact nonlinearly. The class of multiplicative networks

comprises such widely known ...
more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>Scott Aaronson

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Gregory Valiant, Paul Valiant

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science, and in various real-life statistical tasks.

The original distribution testing model relies on samples drawn independently from the distribution ... more >>>