All reports by Author Vitaly Feldman:

__
TR14-148
| 8th November 2014
__

Vitaly Feldman, Will Perkins, Santosh Vempala#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
TR12-064
| 10th May 2012
__

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao#### Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

__
TR10-185
| 2nd December 2010
__

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu#### Agnostic Learning of Monomials by Halfspaces is Hard

__
TR10-022
| 23rd February 2010
__

Vitaly Feldman, Homin Lee, Rocco Servedio#### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

__
TR10-018
| 15th February 2010
__

Vitaly Feldman#### A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Revisions: 1

__
TR08-091
| 10th September 2008
__

Vitaly Feldman#### On The Power of Membership Queries in Agnostic Learning

Revisions: 1

__
TR06-066
| 5th May 2006
__

Vitaly Feldman#### On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

__
TR06-059
| 3rd May 2006
__

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami#### New Results for Learning Noisy Parities and Halfspaces

__
TR06-032
| 25th February 2006
__

Vitaly Feldman#### Optimal Hardness Results for Maximizing Agreements with Monomials

__
TR05-127
| 5th November 2005
__

Vitaly Feldman#### Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries

Revisions: 1

Vitaly Feldman, Will Perkins, Santosh Vempala

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

Vitaly Feldman, Homin Lee, Rocco Servedio

Much work has been done on learning various classes of ``simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>>

Vitaly Feldman

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

Vitaly Feldman

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

Vitaly Feldman

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Vitaly Feldman

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

Vitaly Feldman

Producing a small DNF expression consistent with given data is a

classical problem in computer science that occurs in a number of forms and

has numerous applications. We consider two standard variants of this

problem. The first one is two-level logic minimization or finding a minimal

more >>>