{"data":{"id":"10.48550/arxiv.1304.4633","type":"dois","attributes":{"doi":"10.48550/arxiv.1304.4633","prefix":"10.48550","suffix":"arxiv.1304.4633","identifiers":[{"identifier":"1304.4633","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1304.4633"}],"creators":[{"name":"Juba, Brendan","nameType":"Personal","givenName":"Brendan","familyName":"Juba","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"PAC Quasi-automatizability of Resolution over Restricted Distributions"}],"publisher":"arXiv","container":{},"publicationYear":2013,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (cs.LG)","subjectScheme":"arXiv"},{"lang":"en","subject":"Logic in Computer Science (cs.LO)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2013-04-16T22:10:26Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2013-04-18T00:00:35Z","dateType":"Updated","dateInformation":"v1"},{"date":"2013-04","dateType":"Available","dateInformation":"v1"},{"date":"2013","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We consider principled alternatives to unsupervised learning in data mining by situating the learning task in the context of the subsequent analysis task. Specifically, we consider a query-answering (hypothesis-testing) task: In the combined task, we decide whether an input query formula is satisfied over a background distribution by using input examples directly, rather than invoking a two-stage process in which (i) rules over the distribution are learned by an unsupervised learning algorithm and (ii) a reasoning algorithm decides whether or not the query formula follows from the learned rules. In a previous work (2013), we observed that the learning task could satisfy numerous desirable criteria in this combined context -- effectively matching what could be achieved by agnostic learning of CNFs from partial information -- that are not known to be achievable directly. In this work, we show that likewise, there are reasoning tasks that are achievable in such a combined context that are not known to be achievable directly (and indeed, have been seriously conjectured to be impossible, cf. (Alekhnovich and Razborov, 2008)). Namely, we test for a resolution proof of the query formula of a given size in quasipolynomial time (that is, \"quasi-automatizing\" resolution). The learning setting we consider is a partial-information, restricted-distribution setting that generalizes learning parities over the uniform distribution from partial information, another task that is known not to be achievable directly in various models (cf. (Ben-David and Dichterman, 1998) and (Michael, 2010)).","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xMzA0LjQ2MzM8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xMzA0LjQ2MzM8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+SnViYSwgQnJlbmRhbjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+QnJlbmRhbjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5KdWJhPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5QQUMgUXVhc2ktYXV0b21hdGl6YWJpbGl0eSBvZiBSZXNvbHV0aW9uIG92ZXIgUmVzdHJpY3RlZCBEaXN0cmlidXRpb25zPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDEzPC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+RGF0YSBTdHJ1Y3R1cmVzIGFuZCBBbGdvcml0aG1zIChjcy5EUyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChjcy5MRyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5Mb2dpYyBpbiBDb21wdXRlciBTY2llbmNlIChjcy5MTyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBDb21wdXRlciBhbmQgaW5mb3JtYXRpb24gc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDEzLTA0LTE2VDIyOjEwOjI2WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDEzLTA0LTE4VDAwOjAwOjM1WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTMtMDQ8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGNvbnNpZGVyIHByaW5jaXBsZWQgYWx0ZXJuYXRpdmVzIHRvIHVuc3VwZXJ2aXNlZCBsZWFybmluZyBpbiBkYXRhIG1pbmluZyBieSBzaXR1YXRpbmcgdGhlIGxlYXJuaW5nIHRhc2sgaW4gdGhlIGNvbnRleHQgb2YgdGhlIHN1YnNlcXVlbnQgYW5hbHlzaXMgdGFzay4gU3BlY2lmaWNhbGx5LCB3ZSBjb25zaWRlciBhIHF1ZXJ5LWFuc3dlcmluZyAoaHlwb3RoZXNpcy10ZXN0aW5nKSB0YXNrOiBJbiB0aGUgY29tYmluZWQgdGFzaywgd2UgZGVjaWRlIHdoZXRoZXIgYW4gaW5wdXQgcXVlcnkgZm9ybXVsYSBpcyBzYXRpc2ZpZWQgb3ZlciBhIGJhY2tncm91bmQgZGlzdHJpYnV0aW9uIGJ5IHVzaW5nIGlucHV0IGV4YW1wbGVzIGRpcmVjdGx5LCByYXRoZXIgdGhhbiBpbnZva2luZyBhIHR3by1zdGFnZSBwcm9jZXNzIGluIHdoaWNoIChpKSBydWxlcyBvdmVyIHRoZSBkaXN0cmlidXRpb24gYXJlIGxlYXJuZWQgYnkgYW4gdW5zdXBlcnZpc2VkIGxlYXJuaW5nIGFsZ29yaXRobSBhbmQgKGlpKSBhIHJlYXNvbmluZyBhbGdvcml0aG0gZGVjaWRlcyB3aGV0aGVyIG9yIG5vdCB0aGUgcXVlcnkgZm9ybXVsYSBmb2xsb3dzIGZyb20gdGhlIGxlYXJuZWQgcnVsZXMuIEluIGEgcHJldmlvdXMgd29yayAoMjAxMyksIHdlIG9ic2VydmVkIHRoYXQgdGhlIGxlYXJuaW5nIHRhc2sgY291bGQgc2F0aXNmeSBudW1lcm91cyBkZXNpcmFibGUgY3JpdGVyaWEgaW4gdGhpcyBjb21iaW5lZCBjb250ZXh0IC0tIGVmZmVjdGl2ZWx5IG1hdGNoaW5nIHdoYXQgY291bGQgYmUgYWNoaWV2ZWQgYnkgYWdub3N0aWMgbGVhcm5pbmcgb2YgQ05GcyBmcm9tIHBhcnRpYWwgaW5mb3JtYXRpb24gLS0gdGhhdCBhcmUgbm90IGtub3duIHRvIGJlIGFjaGlldmFibGUgZGlyZWN0bHkuIEluIHRoaXMgd29yaywgd2Ugc2hvdyB0aGF0IGxpa2V3aXNlLCB0aGVyZSBhcmUgcmVhc29uaW5nIHRhc2tzIHRoYXQgYXJlIGFjaGlldmFibGUgaW4gc3VjaCBhIGNvbWJpbmVkIGNvbnRleHQgdGhhdCBhcmUgbm90IGtub3duIHRvIGJlIGFjaGlldmFibGUgZGlyZWN0bHkgKGFuZCBpbmRlZWQsIGhhdmUgYmVlbiBzZXJpb3VzbHkgY29uamVjdHVyZWQgdG8gYmUgaW1wb3NzaWJsZSwgY2YuIChBbGVraG5vdmljaCBhbmQgUmF6Ym9yb3YsIDIwMDgpKS4gTmFtZWx5LCB3ZSB0ZXN0IGZvciBhIHJlc29sdXRpb24gcHJvb2Ygb2YgdGhlIHF1ZXJ5IGZvcm11bGEgb2YgYSBnaXZlbiBzaXplIGluIHF1YXNpcG9seW5vbWlhbCB0aW1lICh0aGF0IGlzLCAicXVhc2ktYXV0b21hdGl6aW5nIiByZXNvbHV0aW9uKS4gVGhlIGxlYXJuaW5nIHNldHRpbmcgd2UgY29uc2lkZXIgaXMgYSBwYXJ0aWFsLWluZm9ybWF0aW9uLCByZXN0cmljdGVkLWRpc3RyaWJ1dGlvbiBzZXR0aW5nIHRoYXQgZ2VuZXJhbGl6ZXMgbGVhcm5pbmcgcGFyaXRpZXMgb3ZlciB0aGUgdW5pZm9ybSBkaXN0cmlidXRpb24gZnJvbSBwYXJ0aWFsIGluZm9ybWF0aW9uLCBhbm90aGVyIHRhc2sgdGhhdCBpcyBrbm93biBub3QgdG8gYmUgYWNoaWV2YWJsZSBkaXJlY3RseSBpbiB2YXJpb3VzIG1vZGVscyAoY2YuIChCZW4tRGF2aWQgYW5kIERpY2h0ZXJtYW4sIDE5OTgpIGFuZCAoTWljaGFlbCwgMjAxMCkpLjwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/1304.4633","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-11T03:28:38.000Z","registered":"2022-03-11T03:28:39.000Z","published":"2013","updated":"2022-03-11T03:28:39.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1304.4633","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}