Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 22 for “"halfspaces"”.
-
Hardy-Sobolev-Maz'ya inequalities for fractional integrals on halfspaces and convex domains
This thesis will present new results involving Hardy and Hardy-Sobolev-Maz'ya inequalities for fractional integrals. There are two key ingredients to many of these results. The first is the conformal transformation between the upper halfspace and the unit ball. The second is the pseudosymmetric …
-
Extension of Chvátal-Gomory Closure via K-Halfspace closure
… of integer points by using the intersection of k-halfspaces as cutting planes. We prove that there exists examples where there is a significant improvement between the number of three-halfspace closure operations and two-halfspace closure. We also provide simulations on a potential approach to …
-
Halfway to Halfspace Testing
In this thesis I study the problem of testing halfspaces under arbitrary probability distributions, using only random samples. A halfspace, or linear threshold function, is a boolean function f : Rⁿ → {±1} defined as the sign of a linear function; that is, f(x) = sign(Σᵢ wᵢxᵢ - θ) where we refer to …
-
Approximate solutions to the wave equation for a medium with one discontinuity
… that the n dimensional space is divided into two halfspaces with two different wave speeds and that these two halfspaces have an interface where the wave speed is not continuous.
-
Intractability Results for some Computational Problems
… parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even …
-
Testing, Learning, Sampling, Sketching
… useful and natural hypothesis classes (including halfspaces, polynomial threshold functions, intersections of halfspaces, etc.), the sample complexity of testing in the distribution-free model is nearly equal to that of learning. This shows that testing does not give a significant advantage in …
-
Cones of Hyperplane Arrangements
… defined as the intersection of a collection of halfspaces from the arrangement, leading to a notion of Whitney numbers for each cone. This thesis concerns cones of hyperplane arrangement in two ways. First we consider cones within the braid arrangement, consisting of the reflecting hyperplanes …
-
Intractability results for problems in computational learning and approximation
… the accuracy of learning an intersection of two halfspaces with an intersection of t halfspaces. Further, we study the learnability of small DNF formulas, and prove optimal 1/2 + ε inapproximability for the accuracy of learning (i) a two term DNF by a t term DNF, and (ii) an AND under adversarial …
-
Thresholded linear bandits
… learning, structured bandits, and learning halfspaces. To achieve sublinear regret in the presence of exponentially many arms, one method is to exploit the structure of the reward function. However, the presence of an unknown threshold component makes previously known algorithms for …
-
Computational applications of invariance principles
… and basic geometric concept classes such as halfspaces, polynomial threshold functions (PTFs) and polytopes. We develop a reasonably generic framework for obtaining pseudorandom generators (PRGs) from invariance principles and suitably apply the framework to old and new invariance principles …
-
Dynamic problems in computational geometry
… and three dimensions), common intersection of halfspaces (2-D and 3-D), and contour of maximal vectors (2-D and 3-D). The principal techniques exploited are fast merging of substructures, and the use of extra storage. Dynamic geometric search structures based upon the configurations are also …
-
An experimental study of ultrasonic beam reflection from fluid-loaded cylindrical shells
… have concentrated on planar structures, both halfspaces and plates. More recent studies of reflection of sound from cylinders have concentrated on effectively planar incident fields, where the sound wave field does not vary appreciably over the cylinder diameter.</p> <p>The problem discussed …
-
Approximate Range Searching In The Absolute Error Model
… general convex bodies, axis-aligned rectangles, halfspaces, Euclidean balls, and simplices. We examine a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, range emptiness, and range reporting. We apply our data …
-
Exploiting balanced trees in the computation of elementary flux modes via breadth-first search
… flux modes are the intersections of positive halfspaces, or the vertices of a convex polyhedron. Although linear programing has long been used to examine polyhedra, biologists have yet to use linear programming's full functionality to rationally design bacteria. The simplex method is one …
-
Lower bounds in communication complexity and learning theory via analytic methods
… intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model …
-
Sample complexity of robust learning against evasion attacks
… follow by giving a robust learning algorithm for halfspaces on {0,1}<i>n</i>. Finally, since the query complexity for halfspaces on R<i>n</i> is unbounded, we instead consider adversaries with <i>bounded</i> precision and give query complexity upper bounds in this setting as well.</p>
-
A new hybrid numerical scheme for simulating fault ruptures with near fault bulk inhomogeneities
… Modeling the elastodynamic response in these two halfspaces needs to be carried out by an Independent Spectral Formulation before joining them to the strip with the appropriate boundary conditions. Dirichlet and Neumann boundary conditions are imposed on the strip and the two half-spaces, …
-
Practical learning in a private and noisy world
… algorithms for testable proper learning of halfspaces and decision trees, sample-efficient verification protocols for unions of rectangles, and uniformity testers for structured high-dimensional distributions.
-
Some problems related to the polytope illumination
… primitive polytopes. A bounded intersection of halfspaces is a primitive polytope, if omitting any halfspace renders the intersection unbounded. A C-polyhedron P ⊂ E^d is a reduced, d-dimensional intersection of homothets of a smooth, strictly convex body C ⊂ E^d . A fa-C-t of P is a connected …
-
Algorithm design for reliable machine learning
… problem that generalizes the problem of learning halfspaces with Massart noise.In the area of Responsible Machine Learning, we study the notion of replicability as an algorithmic property and introduce the notion of replicable policies in the context of stochastic bandits, one of the canonical …
Page 1 of 2