[{"scopus_import":1,"day":"01","has_accepted_license":"1","publication":"46th International Colloquium on Automata, Languages and Programming","citation":{"chicago":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.","short":"V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.","mla":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77.","ieee":"V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12.","apa":"Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77","ista":"Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.","ama":"Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77"},"page":"77:1-77:12","date_published":"2019-07-01T00:00:00Z","type":"conference","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","text":"A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6725","ddc":["000"],"status":"public","title":"Testing the complexity of a valued CSP language","intvolume":" 132","file":[{"creator":"dernst","file_size":575475,"content_type":"application/pdf","access_level":"open_access","file_name":"2019_LIPICS_Kolmogorov.pdf","checksum":"f5ebee8eec6ae09e30365578ee63a492","date_updated":"2020-07-14T12:47:38Z","date_created":"2019-07-31T07:01:45Z","file_id":"6738","relation":"main_file"}],"oa_version":"Published Version","month":"07","publication_identifier":{"isbn":["978-3-95977-109-2"],"issn":["1868-8969"]},"external_id":{"arxiv":["1803.02289"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"conference":{"name":"ICALP 2019: International Colloquim on Automata, Languages and Programming","end_date":"2019-07-12","location":"Patras, Greece","start_date":"2019-07-08"},"doi":"10.4230/LIPICS.ICALP.2019.77","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:38Z","ec_funded":1,"year":"2019","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"VlKo"}],"author":[{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"date_created":"2019-07-29T12:23:29Z","date_updated":"2021-01-12T08:08:40Z","volume":132},{"date_created":"2019-07-29T12:25:31Z","date_updated":"2023-02-23T12:50:15Z","volume":11627,"author":[{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","first_name":"Michael","last_name":"Walter"}],"publication_status":"published","editor":[{"first_name":"J","last_name":"Buchmann","full_name":"Buchmann, J"},{"full_name":"Nitaj, A","first_name":"A","last_name":"Nitaj"},{"last_name":"Rachidi","first_name":"T","full_name":"Rachidi, T"}],"publisher":"Springer Nature","department":[{"_id":"KrPi"}],"year":"2019","ec_funded":1,"place":"Cham","language":[{"iso":"eng"}],"conference":{"name":"AFRICACRYPT: International Conference on Cryptology in Africa","start_date":"2019-07-09","location":"Rabat, Morocco","end_date":"2019-07-11"},"doi":"10.1007/978-3-030-23696-0_9","quality_controlled":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/068"}],"oa":1,"month":"06","publication_identifier":{"eisbn":["978-3-0302-3696-0"],"issn":["0302-9743","1611-3349"],"isbn":["978-3-0302-3695-3"]},"oa_version":"Preprint","status":"public","title":"Sampling the integers with low relative error","intvolume":" 11627","_id":"6726","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","abstract":[{"lang":"eng","text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so."}],"type":"book_chapter","date_published":"2019-06-29T00:00:00Z","page":"157-180","publication":"Progress in Cryptology – AFRICACRYPT 2019","citation":{"chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9"},"day":"29","article_processing_charge":"No","series_title":"LNCS","scopus_import":"1"},{"_id":"6663","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2019","publication_status":"published","status":"public","title":"Construction of polar codes with sublinear complexity","publisher":"IEEE","intvolume":" 65","author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli"},{"first_name":"Hamed","last_name":"Hassani","full_name":"Hassani, Hamed"},{"full_name":"Urbanke, Rudiger","first_name":"Rudiger","last_name":"Urbanke"}],"related_material":{"record":[{"id":"6729","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T12:50:20Z","date_created":"2019-07-23T07:32:57Z","volume":65,"oa_version":"Preprint","type":"journal_article","abstract":[{"lang":"eng","text":"Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered."}],"issue":"5","extern":"1","publication":"IEEE","citation":{"ista":"Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear complexity. IEEE. 65(5), 2782–2791.","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019.","apa":"Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667","ama":"Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667.","mla":"Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.","short":"M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791."},"oa":1,"external_id":{"arxiv":["1612.05295"]},"main_file_link":[{"url":"https://arxiv.org/abs/1612.05295","open_access":"1"}],"quality_controlled":"1","page":"2782-2791","doi":"10.1109/tit.2018.2889667","date_published":"2019-05-01T00:00:00Z","language":[{"iso":"eng"}],"day":"01","month":"05"},{"abstract":[{"lang":"eng","text":"We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting. "}],"extern":"1","type":"conference","author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli"},{"last_name":"Montanari","first_name":"Andrea","full_name":"Montanari, Andrea"}],"date_created":"2019-07-31T09:31:26Z","date_updated":"2021-01-12T08:08:49Z","oa_version":"Preprint","volume":89,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6747","year":"2019","publication_status":"published","status":"public","title":"On the connection between learning two-layers neural networks and tensor decomposition","publisher":"Proceedings of Machine Learning Research","intvolume":" 89","month":"04","day":"01","article_processing_charge":"No","conference":{"end_date":"2019-04-18","location":"Naha, Okinawa, Japan","start_date":"2019-04-16","name":"AISTATS: Artificial Intelligence and Statistics"},"date_published":"2019-04-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1802.07301"}],"citation":{"ama":"Mondelli M, Montanari A. On the connection between learning two-layers neural networks and tensor decomposition. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. Vol 89. Proceedings of Machine Learning Research; 2019:1051-1060.","apa":"Mondelli, M., & Montanari, A. (2019). On the connection between learning two-layers neural networks and tensor decomposition. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (Vol. 89, pp. 1051–1060). Naha, Okinawa, Japan: Proceedings of Machine Learning Research.","ieee":"M. Mondelli and A. Montanari, “On the connection between learning two-layers neural networks and tensor decomposition,” in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Naha, Okinawa, Japan, 2019, vol. 89, pp. 1051–1060.","ista":"Mondelli M, Montanari A. 2019. On the connection between learning two-layers neural networks and tensor decomposition. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics vol. 89, 1051–1060.","short":"M. Mondelli, A. Montanari, in:, Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 2019, pp. 1051–1060.","mla":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor Decomposition.” Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, vol. 89, Proceedings of Machine Learning Research, 2019, pp. 1051–60.","chicago":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor Decomposition.” In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 89:1051–60. Proceedings of Machine Learning Research, 2019."},"external_id":{"arxiv":["1802.07301"]},"oa":1,"quality_controlled":"1","page":"1051-1060"},{"article_number":"8854897","publication_status":"published","publisher":"IEEE","department":[{"_id":"MaMo"}],"year":"2019","date_created":"2019-07-31T09:51:14Z","date_updated":"2021-01-12T08:08:51Z","volume":67,"author":[{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"full_name":"Condo, Carlo","last_name":"Condo","first_name":"Carlo"},{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco"},{"full_name":"Gross, Warren J","first_name":"Warren J","last_name":"Gross"}],"month":"11","publication_identifier":{"issn":["1053587X"]},"quality_controlled":"1","external_id":{"arxiv":["1903.09203"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.09203"}],"language":[{"iso":"eng"}],"doi":"10.1109/TSP.2019.2944738","type":"journal_article","abstract":[{"text":"Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. ","lang":"eng"}],"issue":"22","status":"public","title":"Rate-flexible fast polar decoders","intvolume":" 67","_id":"6750","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","oa_version":"Preprint","scopus_import":1,"day":"15","article_processing_charge":"No","article_type":"original","publication":"IEEE Transactions on Signal Processing","citation":{"ama":"Hashemi SA, Condo C, Mondelli M, Gross WJ. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 2019;67(22). doi:10.1109/TSP.2019.2944738","ista":"Hashemi SA, Condo C, Mondelli M, Gross WJ. 2019. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 67(22), 8854897.","ieee":"S. A. Hashemi, C. Condo, M. Mondelli, and W. J. Gross, “Rate-flexible fast polar decoders,” IEEE Transactions on Signal Processing, vol. 67, no. 22. IEEE, 2019.","apa":"Hashemi, S. A., Condo, C., Mondelli, M., & Gross, W. J. (2019). Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. IEEE. https://doi.org/10.1109/TSP.2019.2944738","mla":"Hashemi, Seyyed Ali, et al. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing, vol. 67, no. 22, 8854897, IEEE, 2019, doi:10.1109/TSP.2019.2944738.","short":"S.A. Hashemi, C. Condo, M. Mondelli, W.J. Gross, IEEE Transactions on Signal Processing 67 (2019).","chicago":"Hashemi, Seyyed Ali, Carlo Condo, Marco Mondelli, and Warren J Gross. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing. IEEE, 2019. https://doi.org/10.1109/TSP.2019.2944738."},"date_published":"2019-11-15T00:00:00Z"}]