检索结果-内蒙古大学图书馆

IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)

作者： Dinur, Irit Guruswami, Venkatesan Weizmann Inst Sci Dept Appl Math & Comp Sci IL-76100 Rehovot Israel Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA USA

ISBN: (纸本)9780769551357

We develop new techniques to incorporate the recently proposed "short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical "Label Cover + Fourier Analysis" framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs and certain coloring-type problems. In particular, we show a hardness for a variant of hyper-graph coloring (with hyperedges of size 6), with a gap between 2 and exp(2 Omega(root log log N)) number of colors where N is the number of vertices. This is the first hardness result to go beyond the O(logN) barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known O(log log N)-coloring hardness for 2-colorable hypergraphs, and an exponential improvement over the (logN)(Omega(1))-coloring hardness for O(1)-colorable hypergraphs. Stated in terms of "covering complexity," we show that for 6-ary Boolean CSPs, it is hard to decide if a given instance is perfectly satisfiable or if it requires more than 2 Omega(root log log N) assignments for covering all of the constraints. While our methods do not yield a result for conventional hypergraph coloring due to some technical reasons, we also prove hardness of (log N)(Omega(1))-coloring 2-colorable 6-uniform hypergraphs (this result relies just on the long code). A key algebraic result driving our analysis concerns a very low-soundness error testing method for Reed-Muller codes. We prove that if a function beta : F-2(m) -> F-2 is 2(Omega(d)) far in absolute distance from polynomials of degree m-d, then the probability that deg(beta g) <= m-3d/4 for a random degree d/4 polynomial g is doubly exponentially small in d.

关键词： PCP Hardness of approximation hyper graph coloring short code

来源：评论

学校读者我要写书评

暂无评论

SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG codeS

引用

SIAM JOURNAL ON COMPUTING 2017年第1期46卷 132-159页

作者： Guruswami, Venkatesan Harsha, Prahladh Hastad, Johan Srinivasan, Srikanth Varma, Girish Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Tata Inst Fundamental Res Bombay 400005 Maharashtra India Simons Inst Theory Comp Berkeley CA USA KTH Royal Inst Technol S-10044 Stockholm Sweden Indian Inst Technol Dept Math Bombay 400076 Maharashtra India

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the "short code" of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287-1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611-649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on n-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with 2(2 Omega(root loglg n)) colors;coloring a 4-colorable 4-uniform hypergraph with 2(2 Omega(root loglg n)) colors;and coloring a 3-colorable 3-uniform hypergraph with (log n)(Omega(1/log log log n)) colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, (log n)(O(1))Colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1) -colorable hypergraphs, and (log log n)(O(1)) for O(1) -colorable, 3-uniform hypergraphs.

关键词： hardness of approximation hypergraph coloring short code

来源：评论

学校读者我要写书评

暂无评论

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes 14

Super-polylogarithmic hypergraph coloring hardness via low-d...

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Guruswami, Venkatesan Harsha, Prahladh Hastad, Johan Srinivasan, Srikanth Varma, Girish Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Tata Inst Fundamental Res Mumbai Maharashtra India Simons Inst Theory Comp Berkeley CA USA KTH Royal Inst Technol Stockholm Sweden Indian Inst Technol Dept Math Mumbai Maharashtra India

ISBN: (纸本)9781450327107

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the "short code" of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs: Coloring a 2-colorable 8-uniform hypergraph with 2(2 Omega(root log log n)) colors. Coloring a 4-colorable 4-uniform hypergraph with 2(2 Omega(root log log n)) colors. Coloring a 3-colorable 3-uniform hypergraph with (log n)(Omega(1/log log log) (n)) colors. In each of these cases, the hardness results obtained are (at least) superpolynomially stronger (if not exponentially stronger as in the third case) than what was previously known for the respective cases. In fact, prior to this result, (log n)(O(1)) colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1)-colorable hypergraphs. The fundamental bottleneck in obtaining coloring inapproximability results using the low-degree long code was a multipartite structural restriction in the PCP construction of Dinur-Guruswami. We are able to get around this restriction by simulating the multipartite structure implicitly by querying just one partition (albeit requiring 8 queries), which yields our result for 2-colorable 8-uniform hypergraphs. The result for 4-colorable 4-uniform hypergraphs is obtained via a "query doubling" method exploiting additional properties of the 8-query test. For 3-colorable 3-uniform hyper graphs, we exploit the ternary domain to design a test with an additive (as opposed to multiplicative) noise function, and analyze its efficacy in killing high weight Fourier coefficients via the pseudorandom properties of an associated quadratic form. The latter step involves extending the key algebraic ingredient of Dinur-Guruswami concerning testing binary Reed-Muller codes to the ternar

关键词： Hardness of Approximation Hypergraph Coloring short code

来源：评论

学校读者我要写书评

暂无评论

Virtual Calling Number for ESME 3

Virtual Calling Number for ESME

引用

3rd International Conference on Computing for Sustainable Global Development (INDIACom)

作者： Raghavendra, G. Reddy, K. Satyanarayan Cambridge Inst Technol Bangalore Karnataka India Cambridge Inst Technol Dept CSE Bangalore Karnataka India

ISBN: (纸本)9789380544199

Presently, ESME in GSM network uses short code to provide service to Mobile subscriber. This short code is not unique and cannot be used everywhere. The acquiring short code by ESME requires service agreement with Mobile Service Provider and availability. Hence, subscribers of different Mobile service provider use different short code. And also ESME needs to connect with each and every Mobile service provider to offer service. We propose a Virtual Calling Number for ESME to reach out every mobile subscriber of GSM network with a single number. It allows the user to get the service from ESME by using this number. Another major advantage of proposed method is that it just needs to establish connection with only one Mobile Service Provider.

关键词： GS ESME Virtual Calling Number short code SMS

来源：评论

学校读者我要写书评

暂无评论

Innovation in service delivery platform: A case for SMS gateway 17

Innovation in service delivery platform: A case for SMS gate...

引用

10th International Conference on Theory and Practice of Electronic Governance, ICEGOV 2017

作者： Owais, Syed Taha Khanna, Seema Mani, R.S. Messaging Division NIC MeitY New Delhi India NICNET NKN and Messaging NIC MeitY New Delhi India

ISBN: (纸本)9781450348256

Mobile phones have become the ubiquitous and integral part of modern lives, providing human connectivity in a way never before witnessed. This gives us a unique opportunity to build an innovative platform for service delivery to the common citizens of India. Any service delivery platform must meet the benchmark of 4A's- namely Availability, Accessibility, Authenticity and Affordability. This paper attempts to bring forward the idea to build a robust service delivery platform using SMS gateway and the opportunities offered by the technologies and the challenges of implementation and operation and suggest its mitigation. This paper also discusses the unification of SMS with competing technologies like eMail/OBD/IVR/Missed-Call system to architect unified and innovative solutions for government and common citizens. © 2017 ACM.