ETHICAL HACKING CIS 6930
Popular in Course
Popular in Comm Sciences and Disorders
This 21 page Class Notes was uploaded by Aliyah Boyer on Friday September 18, 2015. The Class Notes belongs to CIS 6930 at University of Florida taught by Meera Sitharam in Fall. Since its upload, it has received 9 views. For similar materials see /class/207027/cis-6930-university-of-florida in Comm Sciences and Disorders at University of Florida.
Reviews for ETHICAL HACKING
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/18/15
Geometric Complexity and Applications 015 6930 August 26 September 4 2008 Lecture 1 through 4 Lecturer Drl Meera Sitharam Scribe Venkatakrishnan Ramaswamy 1 Introduction Geometric Complexity is a term that is used in a wide variety of contexts to mean different things We will use this term to broadly refer to the study of computational complexity using different geometric techniques Geometry historically was a study of measurement Analytic Geometry is the study of geometry using the principles of algebra We have studied Analytic Geometry in middlehigh school and it enables us to answer questions such as where does the tangent to a curve at some point intersect a certain other line Algebraic Geometry is the more modern avatar in which we study zeros of polynomials de ned over rings Example 1 Consider the polynomials 12 y2 22 7 r2 and am by c2 d The ideal generated by these polynomials is the set of points on which both these polynomials go to zero In this case geometrically it is the points of intersection of the sphere 12 y2 22 7 r2 0 with the plane az by c2 d 0 While algebraic geometry deals with polynomial equations SemiAlgebraic Geometry deals with polynomial inequalities This involves tools from Real Analysis Functional analysis and measure theory 2 Klein s Erlangen program Felix Klein with his Erlangen program in 1872 showed the link between Geom etry and Abstract Algebrar This program looked at geometry as the study of properties of a space invariant under a given group of transformations Thus geometric properties could be described by the group of transformations under the action of which the properties would remain invariantr Example 2 Euclidean distance between two points is a property that is invari ant under the action of the Euclidean group which is the group of rigid body motions in Euclidean space So in R2 for example the distance between two points rhyl and 12 yg is given by 12 7 2 yg 7 y12 Now suppose we perform the translations given by 1 through 41 the new distance is x 7 102 7 y 12 12a 11 a292b ylib2 V 12 i 112 92 i 902 which is the same as the distance between the pair ofpoints before performing the coordinate transformations ngles for example are preserved under rigid body motions and scaling 21 Geometric Theorem Proving In the Erlangen program the hypothesis and the conclusions of a geometric the orem can be written down as polynomials and a proof of the theorem would be equivalent to showing that if the polynomials corresponding to the hypothesis evaluate to zero then the polynomials corresponding to the conclusion evalu ate to zero This is the problem of ideal membership for polynomials in a ring of invariants for a geometric group In general determining ideal membership for polynomials turns out to be a hard problem tripleexponential However in this case we also have the property that the polynomials are invariant under the action of certain groups The WuRitt decomposition algorithm gives an efficient way to determine ideal membership in this case 3 Hilbert s Nullstellensatz Hilbert s Nullstellensatz German for theorem of zeros is a theorem in al gebraic geometry that is useful in coming up with algorithms for determining ideal membership for polynomials Theorem 1 Pt 6 IP1HlPk if and only if there exist an integer m and multiplying polynomials Q1 Q2 l l Qk such that PET 221 Now given a polynomial Pt it is straightforward to verify if it is in the ideal generated by P1 l l l Pk Suppose we knew the degrees of the multiplying poly nomials Q1 Q2 l l l Qk then constructing the multiplying polynomials would be sufficient to show membership of PE in the ideall To construct the multiply ing polynomials we need to determine coefficients of each of the terms for each multiplying polynomial Taking these as variables simplifying 221 QiPi to group like terms and equating coefficients of corresponding terms on the right and left hand sides we observe that we need to solve a system of linear equa tions in order to nd the m 39 of the 39 39 r 39 which is an easy probleml However in practice the coef cients of the multiplying poly nomials are not known Brownawell 1 derived upper bounds on the degrees of Q1 l l l Qk in terms of the degrees of P1 l l l kl his immediately gives us an algorithm for checking ideal membership For each possible degree up to the Brownawell bound we get a system of linear equations lf atleast one of these systems is consistent then P lies in the ideal generated by P1 l l Pk otherwise it does not We illustrate this with an example Example 3 Let P1212 1 1 P2 121 and 1 through 42 P12512llz7 We wish to determine PE is in the ideal generated by P1 and P2 Further let us assume that the multiplying polynomials have degree atmost 1 Thus et Q1 1 all 111 Q2 agz b2 Now from Hilbert s Nullstellensatz PE is in the required ideal PzQ1P1Q2P2 42gt 512 111 7 alz b112 1 1 agz b221 3 42gt 512 111 7 alz3 a1 b1 2a212 a1 b1 Sag 2b2z b1 3b2 Equating coe cients on the left and righthandside we get the following system of linear equations a10 a1bl2a25 a1b13a22b2ll b13b27 This system turns out to have the unique solution a1 0 b1 1 a2 2 b2 2 Thus Pt lies in the ideal generated by P1 and P2 31 Checking if a set of polynomials does not have a com mon zero It turns out that this problem can also be easily posed as an ideal membership probleml Proposition 2 A set of polynomials do not have a common zero and only if the constant polynomial l is in the ideal generated by the set 4 Reducing Unsatis ability to Ideal Member Ship It turns out that several other problems can be reduced to ideal membership for polynomials Here is one Problem 1 Unsatis ability Given apropositionalformula determine if no truth assignment to its variables makes the formula satis able Unsatis ability is known to be in cONpl To reduce unsatis ability to ideal membershipfor each propositional vari able we construct a polynomial Pl z 7 Ila From the propositional formula we construct the polynomial B by replac ing each 39 39 with 39 quot 39 each quot 39 39 wit addition and replace each negation zi with l 7 The formula is unsatis able iff PE is 1 through 43 in the ideal generated by 131132 Pn We can verify if this is so by using Hilbert s Nullstellensatz along with the Brownawell bounds to generate a se quence of linear systems of equations and check if any of them is consistent We illustrate this reduction with an example Example 4 Consider the 3SAT formula 11 V 12 V zg zg V 13 V 14 As described before we have four polynomials P1 P4 with P1 7 Ii This polynomial has two roots 0 and 1 0 corresponding to F andl correspond ing to T and the polynomial PE is constructed such that P evaluates to zero for a particular assignment of 0s and Is to the dis i the propositional formula evaluates to false for the corresponding truth assignment to the propositional variables Thus the polynomial Pt corresponding to the above propositional formula is Pt 11 12 17 7 12 13 14 The idea is that a literal evaluates to False the corresponding expression evaluates to zero Thus a disjunction of literals evaluates to false i in the polynomial each term in the sum is zero which makes the sum equal to zero Similarly a conjunction is false i atleast one of the operands is false and equivalently the product of expressions evaluates to zero atleast one of them is zero From the perspective of complexity theory this reduction enables us to trans fer upper bounds for Unsatis ability from the problem of ideal membership and transfer lower bounds to ideal membership from Unsatis ability 5 Complexity Themes The study of complexity usually has two different kinds of elds One is the study of complexity measures related to computation and information The other is the study of what are called complex systems 51 Complexity measures related to computation and in formation Computational Complexity encompasses the following broad themes 1 P vs NP Some problems don7t have fast algorithms unless PNP 2 NP vs coNP Some problems don7t have short proofs 3 P vs BPP Some problems cannot be derandomized This can be contrasted with the usual mathematical notions of complexity 1 Dimension of representation 2 Sparseness of representation 511 Mulmuley s program Ketan Mulmuley s program 2 to prove Pa NP involves proving lower bounds on some algebraic complexity measure which would imply PfNP 1 through 44 512 An example of a problem for P vs NP lower bounds Problem 2 Consider n points in Rd For d 2 maximize l l such that 3 a set S of points 3 a set L of lines such that any pair of points in S is separated by exactly half the lines in L 513 Automated Geometry Theorem Proving The problem of automated geometry theorem proving may be posed in Eu clidean Geometry7 Projective Geometry or Similarity Geometry This is an example of a problem in the theme of NP vs coNP upper bounds 3 is a good starting point for analytic approaches to this problem and 4 is a good reference for combinatorial and algebraic approaches 52 Complex systems Complex systems is a eld that consists of problems from disparate elds These problems have some common characteristics such as being indecomposable and haVing the property of emergence They include problems from 1 Markets E0 Biological processes such as evolution Weather F90 Dynamical systems 5 lterated function systems 533 G ames 7 Distributed systems 6 Sparse Representations Here is an example of a sparseness question related to analysis Problem 3 Interpolation Given certain points in afunction f pick a small number of basis function from a family of bases and show that for a small num ber of bases de ned appropriately the function cannot be exactly represented by interpolation when 0 Each basis function is independent 0 When the basis functions are not independent The eld of Wavelet Analysis in particular7 and in general Nonlinear Ap proximation Theory are interested in such questions The eld of Geometric Function Theory starting With Dvoretzkyls Theorem is interested in the following type of problem 1 through 45 Problem 4 L quot 39 and quot tion quot Given a high dimensional set of points does there exist a projection onto lower dimensions which distorts it to a small extent This type of problem is also tackled by Principal Components Analysis in Statistics and Machine Learning The Duality Theorem in Geometric Functional Analysis allows us to make nonexistence results imply existence results 7 Algebraic and Analytic approaches to com plexity We will consider analytic and algebraic approaches to the study of complexity and look at the similarities between the two approac esl 71 Analytic approach We study boolean functions which can be written using as few basis functions as possible f EbeMgB abb That is we use as few basis functions as possible in Ml B is a set of simple basis functions If we cannot exactly represent the function with the basis we try to approx imate it EbeMgB abbll lt 5 7 2 Algebraic approaches In the algebraic geometry approach we treat sets as the zero set of a system of polynomial equations of low complexity We might quantify low complexity by specifying bounds on number of equations degree number of variables or number oftermsl We can also use semialgebraic sets or a union of semialgebraic sets The strength of the algebraic approach for complexity theory is that we can ask the the input 6 set and the set E complexity class questions in the same way Here is one way to algebrize Elements linear programs lps geometric constraint systems gcs systems of polynomial equalities and inequalities gx which are somehow special for example belong to an invariant ring of a geometric group or something else Sets Set of lpsgcss that have a common zerodo not have a common zerol Find a system of polynomials 5 whose variables are coef cients of gcs 9 st 59 0 iff 3x 6 F sltlgx 0 F is some eld say the reals Note that this is a family of systems Sm since their number of variables coef cients of g is unbounded since input set of g s is in nite 1 through 46 Now to show g is not in the set we need to show g do not have a common zero which can be converted to an existential statement via Hilberts nullstel lensatz so then we can again get a system of polynomials 5 st Cg 0 iff there is no 1 st 91 0 Complexity Class set of polynomial systemfamilies Sm for which there is a 77few sparse lowdegree77 set of polynomials Pm siti Smg 0 iff Pmg 0 over a eld F P ie 1 Find a family of polynomial systems Csm siti 3P siti C5P 0 iff 3P fewsparselowdegree Siti S F P To show a lower bound show CS do not have a common zeroi Which we can try to convert into an existential statement and then use the trick from earlier to nd a polynomial system siti BS 0 iff Cs does not have a common zero iff S is not in the complexity classi Algebrization is a hurdle to proving complexity lower bounds See 5 for more References l WiDi Brownawell Bounds for the Degrees in the Nullstellensatz Annals of Mathematics 126 1987 pp 571591i E Ki Mulmuley Mi Sohoni Geometric complexity theory I An approach to the P vs NP and related problems SIAM J Computi 312 pp 496526 2001 E ll Ji Schoenberg Metric Spaces and Positive De nite Functions Transac tions of the American Mathematical Society Vol 44 No 3 Nov 1938 pp 522536 E LiMi Blumenthal Theory and Applications of Distance Geometry Oxford 1953 E S Aaronson Al Wigderson Algebrization a new barrier in complexity theory Proci STOC 2008 E CiHi Papadimitriou Computational Complexity Addison Wesley 1993 E l Bourgain Harmonic Analysis and Combinatorics How Much May They Contribute to Each Other in Mathematics Frontiers and Perspectives Vi Arnold Mi Atiyah Pi Lax Bi Mazur edsi AMS 2000 E ll Laba The Kakeya problem and connections to harmonic analysis At http wwwmathubc ca ilabakakeyahtml 1 through 47 9 10 11 12 NH Katz T1 Tao BOUNDS ON ARITHMETIC PROJECTIONS AND APPLICATIONS TO THE KAKEYA CONJECTURE Mathematical Re search Letters 6 625630 1999 A1 Samorodnitsky L1 Trevisani Gowers Uniformity In uence of Variables and PCPs In Proc of 38th STOC ACM 2006 S1 Arora B1 Barak Complexity Theory A Modern Approach Cam bridge University Press expected in 20091 A draft is available at httpwwwcsprincetonedutheorycomplexity 1 T1 Tao lnternational between structure Mathematicians The dichotomy and randomness Congress of presentation At http www math ucla edu taopreprintsSlidesicmslidesZ pdf S1 Khot A1 Naor Nonembeddability theorems via Fourier analysis Math ematische Annalen 334 number 4 821852 2006 http intheory blogspot com200606gowersuniformity html http intheory blogspot com200606analyticalapproachestoszemeredisDB html http 1ucatrevisan wordpress comtagaddit ivecombinatorics http booleanana1ysis blogspot com200702whatsnewinfourieranalysis html A1 A1 Razborov A1 A1 Sherstov The signrank of AC0 FOCS 20081 A A1 Sherstov The unboundederror communication complexity of sym metric functions FOCS 20081 A A1 Sherstov Communication lower bounds using dual polynomials Bul letin of the EATCS 955993 2008 Invited survey1 P1 lnclyk J1 Matousek Lowdistortion embeddings of nite met7ic spaces Handbook of Discrete and Computational Geometry 1 through 48 Recent advances in Complexity CIS 6930CIS 4930 Lecture 13 Lecturer Dr Meera Sitharam October 87 2002 Scribe Erwin Jansen 1 Introduction In today7s lecture we continued with the proof that the clique16 function re quires a monotone circuit of size at least nm The clique16 function outputs a one only when there exists a clique of size In Figure 1 Positive graph Figure 2 Negative graph The idea behind the proof is that we want to show that the class of small monotone functions does not contain the function clique See gure 3 The class of monotone functions is however very diffuse and it is hard to get a grasp on this set In order to get a bit of a grip on this class we are going to look at a dense subset of this class In our case this subset will consist of nice approximator circuits If there were a monotone circuit that computes clique167 then you can always nd a small circuit7 an approximator7 in the neighborhood that does at least as well as cliquegm Now we are going to show that these approximators can7t do cliquekm very well on a particular domain For the domain we wil choose those graphs for which it is very hard to distinguish between a clique16 or not These graphs will be positive and negative test graphs De nition 1 Positive test graph A positive test graph is a graph that barely has clique s and will have only one Is clique De nition 2 Negative test graph A negative test graph is a graph that has many h 7 1 clique s but no h clique This graph is constructed by coloring n vertices with h 7 1 colors Every vertex is assigned a color with equal proba bilityNow we have i vertices with the same color After coloring we connect all pairs of vertices with distinct colors 131 Positive test Negative test mute 3 Axum mandolqu rim CM mixW MmmaimmwaiimmWmmwmm amthmmmlmam mm mayayksmmmkxhudm mmmwicuwmmummmmmm 2 Constructing approximate circuit Thaisymmwewmdnxsgummmmwemmmmm Womach Aymmwmnwmmmhecmmm mm mam A mm mm is ammtuam a A it mammi smw s Mum 3 cm mm A W MW m m mm M t ngpwtmt WWMwMWW a MM mmx Wng um mtmcmwmedm mam mm mm matting mth 3 minimum inmm Wmmmtm m Emmi cw mm mm W Wm a anywhme 1W mm m Hum u mm HLNH swimmmmmmmmmmwmm in aimmmmmmmmmmmmmm W i and Mimi A Ammonium M wwmmm my mm WM M M 9 AW mmlws mt M Vl 150h X S mmmmmmmm age mywwhksmmmaiwkuiymdn mws a x Esme A tit m5 is gumM b mm m em mt vmhkxadlm irdwmz Mum Mmch m m0 mum mwauaypmmmwz m mm mm in mm Since the induction step is not trivial we will look at in more detail We will rst look at the V gate and after that we will examine the construction of an gate 21 Approximating at an V gate Suppose we are converting an V gate in our circuit G Let A and B the func tions that feed into this V gatei By the induction hypothesis these are both approximatorsi Hence A Vi1 and B Willil7 where both sr S in We could simply construct a big approximator of these two by taking an or We would obtain something like Vi 7 where Z X17 in XT7Y17 Hal5 However this approximator could have the a size of at most r s 27m Which exceeds our restriction that we can have at most in distinct setsi Clearly we need to cut down in the size of our approximatori In order to do that we are going to replace several clique indicators from A and B with their common parti To do this we will introduce the concept of a sunflower De nition 5 Sun ower A sun ower is a collection of distinct sets Z17 m Zp called petals such that the intersection Zi U Zj is the same for every pair of dis tinct indices i and j ie39 VISiSPVISjSpV15k5pltZi U Zj Zi U Zkgt We call ZZ U Zj the center of the sun ower The reason for the name sun ower comes from the visualization of the in tersectioni If we look at the gure on t e right we see a sun ower of four sets It is not hard to imagine that the more sets we have7 the more the gure will look like a sun oweri Comnmn Pan Figure 5 A sun ower If we have such a sun ower we can perform an operation called pluckingi Plucking a collection of sets Z07 m Zn is nothing more than replacing the sets 0 m n with their common center We are going to apply this idea to our approximatorsi We are going to pluck the the vertex sets XlquthMls until we cannot pluck it anymore It is easy to see that we can have at most 2m plucking operations The following lemma will be of use Lemma 6 Let L be a collection of sets each of cardinality at most l If lLl gt p 7 1l ll then the collection contains a sun ower with p peta s Proof The proof can be found in 1 and is left as a reading exerciser Using this lemma we can nally get an idea of the values in and pi Setting the values in p 7 1 ll7 we can assure that after the plucking procedure we have at most in vertex setsi Later on we will relate the values 721117 to n7 h of the clique functioni After plucking we get the approximator we are looking forzvigigm 133 S un ower Excercise mm s maymmwxs que39v Cmmmdaypmmwz 2 2 Appxamamng at an A gm Rep ammt We Hume nwm animme mm w mum mmmugkmtmmxmuA wingawsy Weumwawwmmmwmwmmveasmmmsu X u1 gtt msmmmmmmmamsmwm umwwayummwmmtmhadaypmm mswkgmmm m in mm mmmmwmmummgmgw 1x3 dmmuxsdmhkmmmmbyemaymwpummm mmmms Aywmmgmsmmtm mnywnmmaymmwzmm we a Proving the rst lemma mm MVWWMW m MWWMW 1 m alum D P m 902 mm pm we mammme no snwumnm mym mmkmm Nwmwwknmmmmmmtmmxnmx m o 2 mm A gm mgaylusxeymudhy m mm mm m mam pm WWW m mm mm mm amquot m Here n denote all the vertices in the graph and h is the clique on this graph All the l1 vertices are within the clique h Figure 8 l1 in k in n vertices on X1 don7t have an edge That will happen only if they are colored the same The probability that a xed pair has the same color is i and there l are of these pairsl Now the probability that X11 1 is 2 high We have h 7 1 possible colorings of the graph hence there are k 7 1 negative test graphsl Therefor we conclude that the number of negative test graphs for which l X111isat least lt 7gth71n 1 Lemma 8 For every monotone circuit C the number of positive test graphs for which the inequality C S C does not hold is at most si2eC m2 Proof Let A VILI and B Willil be two approximatorsl Now when we nd an approximator for an V we only do plucking When we are plucking we are replacing a large clique indicator by a small clique indicator This procedure can only increase the number of accepted graphsl So it can only go wrong with an gate The replacement procedure will keep the output A 2 as we have seen before in gure 6 and 7 We have seen that plucking does not create any problems either The only step where it can go wrong is the throwing away stage where we throw away those clique indicators Xi U for which lXi U 2 l 1 This is only a problem if the clique indicator we are throwing away output a value of 1 So the l1 or more vertices must all be in the clique as depicted in gure 8 Now the number of graphs such that we are throwing away these l 7 1 vertices is This can happen at most si2eC times if all the gates in C are gatesl It is left as an exercise to prove where the value 7212 stems froml Exercise 1 Extends the proof to include the value m2 References 1 Pl Erdos and R Radol lntersection theorems for systems of sets Journal London Math Society 35285790 1960 135 exercise Geometric Constraints 015 6930 Lecture 3D Realizability Lecturer Drl Meera Sitharam Fall 2006 Scribe Heping Gao We Will present that the forbidden minors for Srealizable graph are K5 and the octahedron You can directly go to Theorem 13 and if necessary refer to the definitions7 lemmas and theorems before it De nition 1 A graph G is drealizable if given any realization 01 pn of the graph in some nite dimensional Euclidean space there exists a realization L11 qn in Ed with the same edge lengths lpi 7 pjl lqi 7 qjl for all i7j E G Note that in the de nition of d realizable allows edges to have length zerol Also note that drealizable is a property of graphs De nition 2 Let G1 and G2 be two graphs both containing a Km as a sub graph The msum of G1 and G2 denoted G1 QB G2 is the graph obtained by identifying the two Km s De nition 3 A graph is mt r ee if it can be obtained through a sequence of msums of Km1 s A graph is a partial mt r ee if it is a subgraph of a m tree Theorem 4 All partial d trees are d realizable De nition 5 A minor of a graph G is any graph obtained from G by a sequence 0 o edge deletions and o edge contractions identify the two vertices belonging to an edge and then remove any loops or multiple edges Theorem 6 If a graph G is d realizable and H is a minor of G then H is d realizable Sketch of Proof Zero length edges are allowed I Theorem 7 The forbidden minors for partial 3trees are K5 the 1skeleton of the octahedron K233 V3 and C5 gtlt C2 see Figure 1 Theorem 8 K5 is not Srealizable Actually7 K5 is overconstrained in 3D but underconstrained in 4 3D Realizability l V KJS Octahdron K7222 V48 aim x gig Figure 1 Forbidden minors for partial 3trees Theorem 9 The 1skeletzm 0f the octahedron K233 is not 3realz39zable Sketch of Proof Assign the following values for K5 shown in Figure 22d12 17d23 17d13 2 d14 7d34 d15 d25 d45 17d25 dgg d45 1 In order to have a solution in 3D7 d55 has to be V or 2 So if we let lt d55 lt 2 then it has no embedding in 3D but have in nite many solutions in 4 4 Figure 2 K23 is not Srealizable The graphs V3 and C5 gtlt C2 are Srealizablei This leaves the possibility that there are other graphs which are not Srealizable but do not have K5 or the octahedron as a minor The following discussion will eliminate this possibility by showing that any graph containing V3 or C5 gtlt C2 as a minor either contains K5 or octahedron as a minor or is Srealizablei Lemma 10 If any edge is added between huhadjacent vertices of V3 the 7 6 sultihg graph has K5 as a minor V8 Figure 3 Graphs of V3 with an added edge contract to K5 23D Realizability2 Sketch of Proof There are two ways to add an edge to V3 up to graph isomorphismi Refer to Figure 3 if we contract the dotted edges the resulting graph is K5 I Lemma 11 If any edge is added between nonadjacent vertices of C5 gtlt C2 the resulting graph has either the octahedron or K5 as a minor Contracts to Octahedron Contracts to Octahedron Contracts to K15 Figure 4 Graphs of C5 gtlt C2 with an added edge contract to octahedron or K5 Sketch of Proof There are three ways to add an edge to C5 gtlt C2 up to graph isomorphismi Refer to Figure 4 if we contract the dotted edges the resulting graph is either octahedron or K5i A graph H is a subdivision of a graph G if H can be obtained from G by replacing every edge ij of G with a path from vertex i to vertex ji Lemma 12 Let H be a graph whose vertices are of maximum degree 5 If a graph G has H as a minor then G contains a subdivision ofH as a subgraph Theorem 13 The forbidden minors for 3realizable graph are K5 and the oc tahedron Sketch of Proof By Theorem 4 all partial 3trees are 3realizableiThat is by Theorem 7 if a graph has no minor of K5 K222V3 or C5 gtlt C2 it is 3realizablei According to Theorem 6 together with Theorem 8 and Theorem 9 if a graph has a minor K5 or K233 then this graph is not 3realizablei Now to nish the proof let s consider the graphs which have minor V3 or C5 gtlt C2 but do not have minor K5 or K233i We will prove in this case the graphs are 3realizable by showing it is a subgraph of 2sum or 3sum of 3realizable graphsi Firstly consider the case that G has V3 as a minor Note that any vertex in V3 has degree right 3 so by Lemma 12 G has a subgraph graph which is a subdivision of V3 and we denote it by Hi Remove H from G we will prove that each connected component in G H is connected in G to exactly one of the subdivided edge of Hi One connected component may only connect to one vertex which is the end vertex of 2 or 3 subdivided edges and we assign any subdivided edge to this component 23D Realizability S If a component did connect to two subdivided edges say ij and 161 Since V3 contains no triangles two of the four relevant verticessay i and must be nonadjacent in Vgi The subdivided edges can be contracted in C so that the path goes from i to k which contradicts Lemma 10 Meanwhile we have the same argument with the case that G has C5 gtlt C2 as a minor Thus we can assign a subdivided edge i j to each of the components For any subdivided edge ijwe can add an edge ij to G if edge ij is not in Cr So we can get a new graph by adding this kind of edges This new graph is the 2sum along the edge ij of smaller graphes such as V3C5 gtlt C2 or partial 3treei So this new graph is 3realizablei G is a subgraph of this new graph so G is 3realizablei Now we discussed all the cases and nished the proo i A characterization of 3realizable graphs is every 3realizable graph is a subgraph of a graph that can be obtained by a sequence of 3sums and 2sums involving K4V3 and C5 gtlt Cgi References 1 Connelly R and Sloughter Mi Realizability of Graphs77 httpwwwmath cornell edu cannellyTealizabilz39tynewpdf 23D Realizability4 Geometric Constraints 015 6930 Lecturer Drl Meera Sitharam Fall 2006 Lecture Johnson Lindenstrauss Lemma and Embedding the diamond Scribe Heping Gao 1 Embedding the diamond graph in LP and di mension reduction in L1 De nition 1 G0 consists of a single edge of length 1 Cl is obtained from Cpl as follows Given an edge u7v E Eclil it is replaced by a quadrilateral uavb with edge lengths 2 11 In what follows u7 v is called an edge of level i 7 l and a7 12 is called the level i antiedge corresponding to u7v e ma 2 Fixl lt pg 2 and17y727w 6 LP Then Hyizllffk oil lziw g S H95 9H Hy 70H llw 2H H2 Ill Please refer to 2 for the proof of Lemma 2 Lemma 3 Let Ai denote the set of antiedges at level i and let 37 t VG0 thenfor l ltp 2 andfor any f Gk ALP k Hf8ftll p71z Z Hfrfyll S Z Hfrfyll i391ryEAI wyEEGk Sketch of Proof Let a7 12 be an edge of level i and c7 d its corresponding antiedger By Lemma 27 MW 7 mm p 7 1Hfc 7 mu MM 7 mu W 7 fcH W 7 fallp W 7 mm summing over all edges and all i 7 7 1 yields the desired result by noting that the terms corresponding to my 6 cancel for i 07 7 kill I Theorem 4 For any 1 lt p S 2 any embedding of Gk into L1 incurs distortion at least sqrtl P 1h Sketch of Proof Let f Gk A L1 be a nonexpansive Dembeddingl Since lAil 4i 1 and the length of a level i antiedge is 214 apply Lemma 3 yields L51 lt 1 Johnson Lindenstrauss Lemma and Embedding the diamond graph in Lpl graph in LP 2 An elementary proof of the JohnsonLindenstrauss Lemma Theorem 5 JohnsonLindenstrauss lemma For any 0 lt e lt l and any integer n let h be a positive integer st h gt 4622 7 633 llnn Then for any set V ofn points in Rd there is a map f Rd 7 Rk st for all uv E lt17 eHu7vH2 MM 7 fvH2 lt1egtHu7 vHQ Further this map can be found in randomized polynomial time Let X1 Xd be d independent N0 1 random variables and let Y Xh Xdl Let vector Z 6 Rk be the projection of Y onto its first It coordinates and let L Clearly the expected length n EL hdl Then we have the following lemma Lemma 6 Let k lt d Then a If lt 1 then PrlL Bicd 6W1 7 d fWMQ men 7 B 1116 a If gt1 then PrlL 2 Bicd 6W1 7 d fWMQ men 7 B 1116 Details of the proof of Lemma 6 can be found in 1 Sketch of Proof Theorem 5 Only need to consider the case d gt kl Take a random k dimensional subspace S and let 1 be the projection ofvertex vi 6 V into Squot Then setting L H1471 and h hdH1 7vH2 and applying Lemma6 we have PrL S l7eh S ln2 and PrL 2 1 ei S ln2l Now choose the map d So for fixed pair i j the distortion 7 7 ijQ does not lie in the range 17 61 6 is at most n2 sing the trivial union bound the chance that some pair of vertices gtlt 2n2 l 7 Hence f has the suffers a large distortion is at most 7 desired properties with probability at least lnl Repeating this projection 0n times can boost the success probability to any desired constant and give us the claimed randomized polynomial time algorithml References l Dasgupta S and Gupta A An elemen tary pro of the Johnson Lindenstrauss Lemma77 0 httpciteseer istpsu edudasguptaggelementary html 2 Lee J and Naor AlAuthorName Embedding the diamond graph in LI and dimension reduction in L177 Manuscript June 2005 httpciteseeristpsueduleeU embeddinghtml JohnsonLindenstrauss Lemma and Embedding the diamond graph in LpQ Geometric Constraints 015 6930 Lecture LSH Based on p Stable Distribution Lecturer Dr Meera Sitharam Fall 2006 Scribe Heping Gao The problem will be discussed here is given objects represented as points in Rd and a distance metric which is used to measure similarity of objects how to perform indexing or similarity searching for query objects The dimensionality d ranges anywhere from tens to thousands Note that the lowdimensional case say the dimensionality d equal to 2 or 3 is wellsolved so the main issues is that of dealing with a large number of dimensions The key idea of localitysensitive hash L5H is to hash the points using several hash functions so as to ensure that for each function the probability of collision is much higher for objects which are close to each other than for those which are far apart Then one can determine near neighbors by hashing the query point and retrieving elements stored in buckets containing that point Since the LSH is a hashingbased scheme it can be naturally extended to the dynamic setting ie when insertion and deletion operations also need to be supported This avoids the complexity of dealing with tree structures when the data is dynamic This paper presented a novel version of the LSH algorithm It works for the R c iNN problem where the goal is to report a point within distance R from L The advantages of the new algorithm is o For the lg norm its query time is 0dnpc logn where pc lt 10 for c 6 110 o It is simple and quite easy to implement o It works for any 1 norm as long as p 6 02 Speci cally it is shown in the paper that for any p 6 02 and 7 gt 0 there exists an algorithm for R c 7 NN under S which uses Odn npr space with query time 0n 7 log1 n where p S 1 7 mazcip Let M X d be any metric space and v E X The ball of radius 7 centered at v is de ned as Bv39r q E Xldvq S 7 For a domain 5 of the points set with distance measure D an L5H family is de ned as De nition 1 A family H h S A U is called 7 17 2p1p2 7 sensitive for D if for any 1 q E o ifv E Bq39r1 then PTHhq hv 2 pl 0 ifv g Bq39r2 then PTHhq hv S p2 LSH Based on pStable Distributionl In order for a localitysensitive hash L5H family to be useful it has to satisfy inequalities p1 gt p2 and r1 lt rgi Theorem 2 Suppose there is a RcRp1p2 7 sensitive family H for a dis tance measure D Then there exists an algorithm for R c7N N under measure D which use Odnn1p space with query time dominated by 0n 7 distance computations and 0n1 log1p2 n evaluations of hash functions from H where 7 lnlp1 p 7 lnlpz39 The following notes will show how to get the hash familyi De nition 3 A distribution D over R is called pstable if there exists p 2 0 such that for any n real numbers v1 vn an d variables 1Xn with distribution D the random variable viXi has the same distribution as the variable lv 1pX where X is a random variable with distribution D Each hash function is given as hmb v where a is a d dimensional vector with entries chosen independently from a pstable distribution and b is a real number chosen uniformly from the range 0rli So each hash function is indexed by random a and bi Since stable distribution exist for any p E 0 2 we can nd hash family for all p E 0 2 by this way Now let s have a look at the property of hash function habvi For two vectors v1 v2 let c Hvl 7 vgllpi For a random vector a whose entries are drawn from a pstable distribution a v1 7 a v2 is distributed as cX where X is a random variable drawn from a pstable distributioni Since b is drawn uniformly from 0 r it is easy to see that pltcgt 7 Pullman 7 habv2l 7 I fpltgtlt17 wt Here fpt denotes the probability density function of the absolute value of the pstable distributioni As per De nition 1 the family of hash functions above is r1 rlc plpc7 sensitivei References 1 Datar Mr and lmmorlica Ni and lndyk Pi and Mirrokni Vi LocalitySensitive hashing Scheme Based on pStable Distribution wwwmitedu mirroknipstableps LSH Based on pStable Distribution2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'