@inproceedings{6747, abstract = {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. }, author = {Mondelli, Marco and Montanari, Andrea}, booktitle = {Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics}, location = {Naha, Okinawa, Japan}, pages = {1051--1060}, publisher = {Proceedings of Machine Learning Research}, title = {{On the connection between learning two-layers neural networks and tensor decomposition}}, volume = {89}, year = {2019}, } @article{6750, abstract = {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. }, author = {Hashemi, Seyyed Ali and Condo, Carlo and Mondelli, Marco and Gross, Warren J}, issn = {1053587X}, journal = {IEEE Transactions on Signal Processing}, number = {22}, publisher = {IEEE}, title = {{Rate-flexible fast polar decoders}}, doi = {10.1109/TSP.2019.2944738}, volume = {67}, year = {2019}, } @article{6759, abstract = {We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions.}, author = {Jelínek, Vít and Töpfer, Martin}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, number = {3}, publisher = {Electronic Journal of Combinatorics}, title = {{On grounded L-graphs and their relatives}}, doi = {10.37236/8096}, volume = {26}, year = {2019}, } @inproceedings{6822, abstract = {In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.}, author = {Avni, Guy and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Novotny, Petr}, booktitle = { Proceedings of the 13th International Conference of Reachability Problems}, isbn = {978-303030805-6}, issn = {0302-9743}, location = {Brussels, Belgium}, pages = {1--12}, publisher = {Springer}, title = {{Bidding games on Markov decision processes}}, doi = {10.1007/978-3-030-30806-3_1}, volume = {11674}, year = {2019}, } @inproceedings{6887, abstract = {The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. }, author = {Chatterjee, Krishnendu and Dvorák, Wolfgang and Henzinger, Monika H and Svozil, Alexander}, booktitle = {Leibniz International Proceedings in Informatics}, location = {Amsterdam, Netherlands}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Near-linear time algorithms for Streett objectives in graphs and MDPs}}, doi = {10.4230/LIPICS.CONCUR.2019.7}, volume = {140}, year = {2019}, }