Pages that link to "Item:Q1887713"
From MaRDI portal
The following pages link to Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) (Q1887713):
Displayed 36 items.
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length (Q368235) (← links)
- The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions (Q645127) (← links)
- Learning unions of \(\omega(1)\)-dimensional rectangles (Q950197) (← links)
- Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning (Q1009287) (← links)
- The hardest halfspace (Q1983325) (← links)
- On XOR lemmas for the weight of polynomial threshold functions (Q2280318) (← links)
- Proper learning of \(k\)-term DNF formulas from satisfying assignments (Q2323349) (← links)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities (Q2347795) (← links)
- On PAC learning algorithms for rich Boolean function classes (Q2382283) (← links)
- The unbounded-error communication complexity of symmetric functions (Q2428632) (← links)
- Solving linear constraints over real and rational fields (Q2452760) (← links)
- Maximum patterns in datasets (Q2478429) (← links)
- Degree-uniform lower bound on the weights of polynomials with given sign function (Q2510769) (← links)
- Polynomial threshold functions and Boolean threshold circuits (Q2514146) (← links)
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits (Q3448791) (← links)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070) (← links)
- The Power of Asymmetry in Constant-Depth Circuits (Q4562278) (← links)
- What Circuit Classes Can Be Learned with Non-Trivial Savings? (Q4638080) (← links)
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ (Q4957911) (← links)
- (Q5009530) (← links)
- Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors (Q5025767) (← links)
- Approximate Degree in Classical and Quantum Computing (Q5060675) (← links)
- (Q5091179) (← links)
- Sign rank vs discrepancy (Q5092468) (← links)
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ (Q5117375) (← links)
- Algorithmic Polynomials (Q5138783) (← links)
- (Q5140844) (← links)
- (Q5158501) (← links)
- (Q5743387) (← links)
- (Q5875514) (← links)
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (Q5891428) (← links)
- Exact learning of DNF formulas using DNF hypotheses (Q5916223) (← links)
- On the modulo degree complexity of Boolean functions (Q5918108) (← links)
- Hardness of approximate two-level logic minimization and PAC learning with membership queries (Q5920702) (← links)
- On (simple) decision tree rank (Q6050134) (← links)
- Linear threshold functions in decision lists, decision trees, and depth-2 circuits (Q6072201) (← links)