{"data":{"id":"10.48550/arxiv.1001.4137","type":"dois","attributes":{"doi":"10.48550/arxiv.1001.4137","prefix":"10.48550","suffix":"arxiv.1001.4137","identifiers":[{"identifier":"1001.4137","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1001.4137"}],"creators":[{"name":"Shenvi, Sagar","nameType":"Personal","givenName":"Sagar","familyName":"Shenvi","affiliation":[],"nameIdentifiers":[]},{"name":"Dey, Bikash Kumar","nameType":"Personal","givenName":"Bikash Kumar","familyName":"Dey","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"On the solvability of 3-source 3-terminal sum-networks"}],"publisher":"arXiv","container":{},"publicationYear":2010,"subjects":[{"lang":"en","subject":"Information Theory (cs.IT)","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":"2010-01-23T07:59:53Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2010-02-26T11:34:21Z","dateType":"Updated","dateInformation":"v1"},{"date":"2010-02-09T11:20:14Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2010-02-26T11:34:21Z","dateType":"Updated","dateInformation":"v2"},{"date":"2010-04-19T12:50:25Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2015-03-13T19:08:48Z","dateType":"Updated","dateInformation":"v3"},{"date":"2010-01","dateType":"Available","dateInformation":"v1"},{"date":"2010","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We consider a directed acyclic network with three sources and three terminals such that each source independently generates one symbol from a given field $F$ and each terminal wants to receive the sum (over $F$) of the source symbols. Each link in the network is considered to be error-free and delay-free and can carry one symbol from the field in each use. We call such a network a 3-source 3-terminal {\\it $(3s/3t)$ sum-network}. In this paper, we give a necessary and sufficient condition for a $3s/3t$ sum-network to allow all the terminals to receive the sum of the source symbols over \\textit{any} field. Some lemmas provide interesting simpler sufficient conditions for the same. We show that linear codes are sufficient for this problem for $3s/3t$ though they are known to be insufficient for arbitrary number of sources and terminals. We further show that in most cases, such networks are solvable by simple XOR coding. We also prove a recent conjecture that if fractional coding is allowed, then the coding capacity of a $3s/3t$ sum-network is either $0,2/3$ or $\\geq 1$.","descriptionType":"Abstract"},{"description":"Major revision in the structure of the paper. 24 pages, 15 figures. Shorter version accepted to ISIT 2010","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xMDAxLjQxMzc8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xMDAxLjQxMzc8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+U2hlbnZpLCBTYWdhcjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+U2FnYXI8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+U2hlbnZpPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkRleSwgQmlrYXNoIEt1bWFyPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5CaWthc2ggS3VtYXI8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+RGV5PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5PbiB0aGUgc29sdmFiaWxpdHkgb2YgMy1zb3VyY2UgMy10ZXJtaW5hbCBzdW0tbmV0d29ya3M8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTA8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5JbmZvcm1hdGlvbiBUaGVvcnkgKGNzLklUKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTAtMDEtMjNUMDc6NTk6NTNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTAtMDItMjZUMTE6MzQ6MjFaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAxMC0wMi0wOVQxMToyMDoxNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAxMC0wMi0yNlQxMTozNDoyMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDEwLTA0LTE5VDEyOjUwOjI1WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDE1LTAzLTEzVDE5OjA4OjQ4WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTAtMDE8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MzwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGNvbnNpZGVyIGEgZGlyZWN0ZWQgYWN5Y2xpYyBuZXR3b3JrIHdpdGggdGhyZWUgc291cmNlcyBhbmQgdGhyZWUgdGVybWluYWxzIHN1Y2ggdGhhdCBlYWNoIHNvdXJjZSBpbmRlcGVuZGVudGx5IGdlbmVyYXRlcyBvbmUgc3ltYm9sIGZyb20gYSBnaXZlbiBmaWVsZCAkRiQgYW5kIGVhY2ggdGVybWluYWwgd2FudHMgdG8gcmVjZWl2ZSB0aGUgc3VtIChvdmVyICRGJCkgb2YgdGhlIHNvdXJjZSBzeW1ib2xzLiBFYWNoIGxpbmsgaW4gdGhlIG5ldHdvcmsgaXMgY29uc2lkZXJlZCB0byBiZSBlcnJvci1mcmVlIGFuZCBkZWxheS1mcmVlIGFuZCBjYW4gY2Fycnkgb25lIHN5bWJvbCBmcm9tIHRoZSBmaWVsZCBpbiBlYWNoIHVzZS4gV2UgY2FsbCBzdWNoIGEgbmV0d29yayBhIDMtc291cmNlIDMtdGVybWluYWwge1xpdCAkKDNzLzN0KSQgc3VtLW5ldHdvcmt9LiBJbiB0aGlzIHBhcGVyLCB3ZSBnaXZlIGEgbmVjZXNzYXJ5IGFuZCBzdWZmaWNpZW50IGNvbmRpdGlvbiBmb3IgYSAkM3MvM3QkIHN1bS1uZXR3b3JrIHRvIGFsbG93IGFsbCB0aGUgdGVybWluYWxzIHRvIHJlY2VpdmUgdGhlIHN1bSBvZiB0aGUgc291cmNlIHN5bWJvbHMgb3ZlciBcdGV4dGl0e2FueX0gZmllbGQuIFNvbWUgbGVtbWFzIHByb3ZpZGUgaW50ZXJlc3Rpbmcgc2ltcGxlciBzdWZmaWNpZW50IGNvbmRpdGlvbnMgZm9yIHRoZSBzYW1lLiBXZSBzaG93IHRoYXQgbGluZWFyIGNvZGVzIGFyZSBzdWZmaWNpZW50IGZvciB0aGlzIHByb2JsZW0gZm9yICQzcy8zdCQgdGhvdWdoIHRoZXkgYXJlIGtub3duIHRvIGJlIGluc3VmZmljaWVudCBmb3IgYXJiaXRyYXJ5IG51bWJlciBvZiBzb3VyY2VzIGFuZCB0ZXJtaW5hbHMuIFdlIGZ1cnRoZXIgc2hvdyB0aGF0IGluIG1vc3QgY2FzZXMsIHN1Y2ggbmV0d29ya3MgYXJlIHNvbHZhYmxlIGJ5IHNpbXBsZSBYT1IgY29kaW5nLiBXZSBhbHNvIHByb3ZlIGEgcmVjZW50IGNvbmplY3R1cmUgdGhhdCBpZiBmcmFjdGlvbmFsIGNvZGluZyBpcyBhbGxvd2VkLCB0aGVuIHRoZSBjb2RpbmcgY2FwYWNpdHkgb2YgYSAkM3MvM3QkIHN1bS1uZXR3b3JrIGlzIGVpdGhlciAkMCwyLzMkIG9yICRcZ2VxIDEkLjwvZGVzY3JpcHRpb24+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJPdGhlciI+TWFqb3IgcmV2aXNpb24gaW4gdGhlIHN0cnVjdHVyZSBvZiB0aGUgcGFwZXIuIDI0IHBhZ2VzLCAxNSBmaWd1cmVzLiBTaG9ydGVyIHZlcnNpb24gYWNjZXB0ZWQgdG8gSVNJVCAyMDEwPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/1001.4137","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-15T19:29:12.000Z","registered":"2022-03-15T19:29:12.000Z","published":"2010","updated":"2022-03-15T19:29:12.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1001.4137","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}