I partiell funktionsförlängning får vi en partiell funktion som består av n-punkter från en domän och ett funktionsvärde vid varje punkt. Vårt mål är att avgöra om denna partiella funktion kan utvidgas till en funktion som definieras på domänen, som dessutom uppfyller en given egenskap, såsom konvexitet. Detta grundläggande problem ligger till grund för forskningsfrågor inom många områden, till exempel lärande, fastighetstestning och spelteori. Vi studerar formellt problemet med att utöka partiella funktioner för att tillfredsställa grundläggande egenskaper i kombinatorisk optimering, med fokus på övre och nedre gränser för förlängning och tillämpningar till lärande och testning av egendom. • För subadditiva funktioner visar vi att förlängningsproblemet är coNP-komplett, och vi ger snäva gränser för approximabiliteten. Vi ger också en förbättrad nedre gräns för att lära subadditiva funktioner. Tidigare, Balcan et al. (2012) gav en lägre gräns för detta problem. Vi ger också de första icke-triviala testarna för subadditiva och XOS-funktioner. • För submodulära funktioner, visar vi att om en partiell funktion kan utökas till en submodulär funktion på lattice stängning 1 av den partiella funktionen, kan den utvidgas till en submodulär funktion på hela domänen. Vi får algoritmer för att bestämma förlängning i ett antal fall, inklusive om n är en konstant, eller punkterna är nästan samma storlek. Resultatet använder ett kombinatoriskt certifikat för icke-extendibilitet som vi kallar ett fyrkantigt certifikat. Seshadhri och Vondrak (2014) ger tidigare en karakterisering i termer av sökväg certifikat. Utökningsbarhetens komplexitet är i allmänhet olöst. • Slutligen, för konvexa funktioner i R m, visar vi en intressant juxtaposition: medan vi kan avgöra förekomsten av en förlängning effektivt, beräkning värdet av en brett studerade konvex förlängning vid en given punkt är starkt NP-hård. * Arbetet stöds delvis av en Ramanujan gemenskap. E-post: umang@tifr.res.in † E-post: gunjan.kumar@tifr.res.in 1 Lattice stängning LC(D) av uppsättning av punkter D är den minimala uppsättning som innehåller D och är stängd under union och korsning.
I ett separat dokument studerar vi partiell funktionsförlängning till submodulära, subadditiva och konvexa funktioner, som visar resultat på komplexiteten samt tillämpningar för inlärning och testning av egendom REF.
Partial Function Extension with Applications to Learning and Property Testing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}