A central goal of theoretical computer science is to characterize the limits of efficient computation in a variety of models. We pursue this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to rigorously explain why computers cannot master some prediction tasks or learn from past experience. While communication and learning may seem to have little in common, they turn out to be closely related, and much insight into both can be gained by studying them jointly. Such is the approach pursued in this thesis. We answer several fundamental questions in communication complexity and learning theory and in so doing discover new relations between the two topics. A consistent theme in our work is the use of analytic methods to solve the problems at hand, such as approximation theory, Fourier analysis, matrix analysis, and duality. We contribute a novel technique, the pattern matrix method, for proving lower bounds on communication. Using our method, we solve an open problem due to Krause and Pudlák (1997) on the comparative power of two well-studied circuit classes: majority circuits and constant-depth AND/OR/NOT circuits. Next, we prove that the pattern matrix method applies not only to classical communication but also to the more powerful quantum model. In particular, we contribute lower bounds for a new class of quantum communication problems, broadly subsuming the celebrated work by Razborov (2002) who used different techniques. In addition, our method has enabled considerable progress by a number of researchers in the area of multiparty communication. Second, we study unbounded-error communication, a natural model with applications to matrix analysis, circuit complexity, and learning. We obtain essentially optimal lower bounds for all symmetric functions, giving the first strong results for unbounded-error communication in years. Next, we resolve a longstanding open problem due to Babai, Frankl, and Simon (1986) on the comparative power of unbounded-error communication and alternation, showing that [mathematical equation]. The latter result also yields an unconditional, exponential lower bound for learning DNF formulas by a large class of algorithms, which explains why this central problem in computational learning theory remains open after more than 20 years of research. We establish the computational intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model (under standard cryptographic assumptions), and various analytic models. We also prove that the intersection of even two halfspaces on {0,1}n cannot be sign-represented by a polynomial of degree less than [Theta](square root of n), which is an exponential improvement on previous lower bounds and solves an open problem due to Klivans (2002). We fully determine the relations and gaps among three key complexity measures of a communication problem: product discrepancy, sign-rank, and discrepancy. As an application, we solve an open problem due to Kushilevitz and Nisan (1997) on distributional complexity under product versus nonproduct distributions, as well as separate the communication classes PPcc and UPPcc due to Babai, Frankl, and Simon (1986). We give interpretations of our results in purely learning-theoretic terms. / text

L'accès à l'information géographique sous forme électronique s'ouvre de plus en plus au grand publique. Des interfaces intuitives ne nécessitant pas ou peu d'apprentissage apparaissent alors dans le domaine. Néanmoins, lorsqu'il s'agit de spécifier plus finement l'information recherchée, le pouvoir expressif de ces interfaces est limité. <br />Le projet Antéserveur Géographique propose un environnement complet pour permettre d'exprimer une requête de manière bi-modale (schéma + étiquette textuelle). Nous verrons alors les problèmes d'ambiguïtés dûs aux différents sens qu'une telle modalité peut véhiculer. Pour lever ces ambiguïtés notre interface propose un fonctionnement multimodal utilisant notamment la complémentarité du texte et du schéma grâce à une interaction contrôlée, celle-ci reposant sur un mécanisme appelé glissement de sens. Le mode textuel et les glissements de sens nécessitent une analyse spatiale adaptée du schéma. <br />Nous aborderons alors le domaine de l'analyse spatiale qualitative, au coeur de ce travail de recherche, dans lequel une utilisation récurrente par centre d'intérét du modèle 9-intersections de M.J. Egenhofer est proposée. <br />Grâce à cette méthode, nous disposons d'un modèle d'analyse spatiale unique permettant de relever différentes contraintes relevées jusqu'ici par des modèles distincts et sans lien. C'est cette unité qui nous permet de mettre en oeuvre notre mécanisme de glissement de sens. Nous présenterons alors notre réalisation informatique qui met en oeuvre ces mécanismes et nous permet ainsi de tester les concepts de multimodalité et de glissement de sens présentés plus haut.

The accident rate at an intersection is one attribute used to evaluate the hazard associated with the intersection. Two techniques traditionally used to make such evaluations are the rate-quality technique and a technique based on the confidence interval of classical statistics. Both of these techniques label intersections as hazardous if their accident rate is greater than some critical accident rate determined by the technique. An alternative technique is one based on a Bayesian analysis of available accident number and traffic volume data. In contrast to the two classic techniques, the Bayesian technique identifies an intersection as hazardous based on a probabilistic assessment of accident rates. The goal of this thesis is to test and compare the ability of the three techniques to accurately identify traffic intersections known to be hazardous. Test data is generated from an empirical distribution of accident rates. The techniques are then applied to the generated data and compared based on the simulation results.

M.Ing. (Mechanical Engineering) / The purpose of this study was to investigate the accuracy of SOAP84-simulations of delay and percentage stops at isolated signalized intersections. In the application, capacity was distinguished in terms of lane configuration only. Results at the intersections showed SOAP overestimating both delay and percentage stops by as much as 100%. It is recommended that the same investigations be repeated with more accurate information on the capacity of the intersections.

When simulating air flows in an urban environment, for e.g. pollutant dispersion investigations, today's main tool is advanced computational fluid dynamics simulations. These simulations take a lot of time and resources to perform, even for small geometries. In some situations, one would like to be able to run approximate simulations, possibly with large geometries, without such a significant investment. The model described in this thesis is a graph network model which have streets and intersections of an urban environment modeled as connections and nodes in a graph. The model uses a pressured pipe model, based on the Darcy-Weisbach equation, to simulate air flow in the network. Such a model requires only rough measurements of the urban geometry and an estimated Darcy's friction factor, to be able to solve the system. Furthermore, using the same rough geometrical parameters, together with shear velocity, the model solves atmospheric exchange rates of the streets. Intersections play a major role when investigating urban dispersion. The way this model deals with dispersion in any complex intersections, represented by single nodes, is by using wind direction variance together with a distribution parameter based on computational fluid dynamics intersection simulations made in Comsol Multiphysics - also present in this paper. Using the simple model described above, I have simulated urban air flows in a complex urban geometry of a part of Paris. This specific geometry has already been investigated by computational fluid dynamics simulations as well as wind tunnel experiments. By comparing the computational fluid dynamics simulation with my model, I have validated its accuracy. 40% and 45% of all streets reach a relative and absolute error below 25% respectively. Directions of the street velocities have been simulated with approximately 90% accuracy - with distinct error indications. Atmospheric exchange rates of the streets are within an order of magnitude accurate, however, showing a systematic error by overestimating the vast majority of the exchange rates. The model could become even better by covering error sources discussed in the discussion section. Excess theory for simulating each of the above-described flows is presented, which might change the results. For example, slightly altering the modeling of the atmospheric exchange rate might fix the overestimation offset we have seen. Potential error sources could be the varying building heights and the streets angle relative the overlaying wind direction. The pressured pipe simulated flows have shown tendencies to be bad at picking up the effects of high/low buildings following low/high buildings, as well as accurately capture the behavior of streets close to perpendicular to the wind direction. Main streets with plenty of exits have been modeled with intersections at each exit, which results in strong flow variation along a street that should have a flow close to constant. Solving main streets like this separately could improve this behavior drastically.

Este artículo presenta la evaluación del tráfico vehicular en dos intersecciones semaforizadas ubicadas en la ciudad de Lima; una de las principales ciudades del mundo con gran congestión vehicular; mediante un modelo microscópico desarrollado con el software Vissim 9.0. La finalidad de esta investigación es proponer la implementación de un sistema de semaforización inteligente para mejorar los niveles de servicio y disminuir la congestión vehicular. El proceso de construcción del modelo consiste en cuatro etapas. Primero, es el trabajo previo, en la cual se realizó la recolección de datos de campo. Luego, se construyó el modelo mediante el software Vissim 9.0. Después, se realizó la calibración y validación del modelo en ambas intersecciones en base a parámetros psicofísicos para certificar que los resultados del modelo se asemejen a las condiciones reales de las intersecciones. Por último, se incorporaron los nuevos flujos futuros en el modelo cada 15 minutos los cuales se simularon y evaluaron con los NS obtenidos, que incorporan la propuesta de mejora. Esencialmente los niveles de servicio de las intersecciones mejoran, determinando cada 15 minutos durante la hora pico nuevos ciclos semaforizados optimizados con el programa Synchro 10.0 aplicados a Vissim 9.0, pasando de un NS E a D, esto se deduce a partir de la disminución de longitudes de colas en todos los accesos y la reducción de las demoras de viaje, las cuales fueron 14% en la Av. Javier Prado – Ca. Las Flores y 24% en la Av. Javier Prado – Ca. Las Palmeras. / This paper presents the evaluation of vehicular traffic on two signalized intersections located in the city of Lima; one of the world's major cities with high traffic congestion; by microscopic model developed with Vissim 9.0 software. The purpose of this research is to propose the implementation of an intelligent traffic signals to improve service levels and reduce traffic congestion. The process of building the model consists of four stages. First, it is the previous work, in which the field data collection was performed. The model was then constructed by Vissim 9.0 software. After, calibration and validation of the model was performed on both intersections based on psychophysical parameters to certify that the model results resemble the actual conditions of intersections. Finally, new future flows were incorporated into the model every 15 minutes which were simulated and evaluated with the NS obtained, incorporating the proposed improvement. Essentially service levels intersections improve, determining every 15 minutes during rush hour new signalized cycles optimized with Synchro 10.0 program applied to Vissim 9.0, from an NS E to D, It follows from decreasing lengths queues at all entrances and reducing travel delays, which were 14% at Av. Javier Prado -. Ca. Las Flores and 24% on Av. Javier Prado -. Ca. Las Palmeras. / Trabajo de investigación

Este artículo presenta la evaluación del tráfico vehicular en dos intersecciones semaforizadas ubicadas en la ciudad de Lima; una de las principales ciudades del mundo con gran congestión vehicular; mediante un modelo microscópico desarrollado con el software Vissim 9.0. La finalidad de esta investigación es proponer la implementación de un sistema de semaforización inteligente para mejorar los niveles de servicio y disminuir la congestión vehicular. El proceso de construcción del modelo consiste en cuatro etapas. Primero, es el trabajo previo, en la cual se realizó la recolección de datos de campo. Luego, se construyó el modelo mediante el software Vissim 9.0. Después, se realizó la calibración y validación del modelo en ambas intersecciones en base a parámetros psicofísicos para certificar que los resultados del modelo se asemejen a las condiciones reales de las intersecciones. Por último, se incorporaron los nuevos flujos futuros en el modelo cada 15 minutos los cuales se simularon y evaluaron con los NS obtenidos, que incorporan la propuesta de mejora. Esencialmente los niveles de servicio de las intersecciones mejoran, determinando cada 15 minutos durante la hora pico nuevos ciclos semaforizados optimizados con el programa Synchro 10.0 aplicados a Vissim 9.0, pasando de un NS E a D, esto se deduce a partir de la disminución de longitudes de colas en todos los accesos y la reducción de las demoras de viaje, las cuales fueron 14% en la Av. Javier Prado – Ca. Las Flores y 24% en la Av. Javier Prado – Ca. Las Palmeras. / This paper presents the evaluation of vehicular traffic on two signalized intersections located in the city of Lima; one of the world's major cities with high traffic congestion; by microscopic model developed with Vissim 9.0 software. The purpose of this research is to propose the implementation of an intelligent traffic signals to improve service levels and reduce traffic congestion. The process of building the model consists of four stages. First, it is the previous work, in which the field data collection was performed. The model was then constructed by Vissim 9.0 software. After, calibration and validation of the model was performed on both intersections based on psychophysical parameters to certify that the model results resemble the actual conditions of intersections. Finally, new future flows were incorporated into the model every 15 minutes which were simulated and evaluated with the NS obtained, incorporating the proposed improvement. Essentially service levels intersections improve, determining every 15 minutes during rush hour new signalized cycles optimized with Synchro 10.0 program applied to Vissim 9.0, from an NS E to D, It follows from decreasing lengths queues at all entrances and reducing travel delays, which were 14% at Av. Javier Prado -. Ca. Las Flores and 24% on Av. Javier Prado -. Ca. Las Palmeras. / Tesis

Este artículo presenta la evaluación del tráfico vehicular en dos intersecciones semaforizadas ubicadas en la ciudad de Lima; una de las principales ciudades del mundo con gran congestión vehicular; mediante un modelo microscópico desarrollado con el software Vissim 9.0. La finalidad de esta investigación es proponer la implementación de un sistema de semaforización inteligente para mejorar los niveles de servicio y disminuir la congestión vehicular. El proceso de construcción del modelo consiste en cuatro etapas. Primero, es el trabajo previo, en la cual se realizó la recolección de datos de campo. Luego, se construyó el modelo mediante el software Vissim 9.0. Después, se realizó la calibración y validación del modelo en ambas intersecciones en base a parámetros psicofísicos para certificar que los resultados del modelo se asemejen a las condiciones reales de las intersecciones. Por último, se incorporaron los nuevos flujos futuros en el modelo cada 15 minutos los cuales se simularon y evaluaron con los NS obtenidos, que incorporan la propuesta de mejora. Esencialmente los niveles de servicio de las intersecciones mejoran, determinando cada 15 minutos durante la hora pico nuevos ciclos semaforizados optimizados con el programa Synchro 10.0 aplicados a Vissim 9.0, pasando de un NS E a D, esto se deduce a partir de la disminución de longitudes de colas en todos los accesos y la reducción de las demoras de viaje, las cuales fueron 14% en la Av. Javier Prado – Ca. Las Flores y 24% en la Av. Javier Prado – Ca. Las Palmeras. / This paper presents the evaluation of vehicular traffic on two signalized intersections located in the city of Lima; one of the world's major cities with high traffic congestion; by microscopic model developed with Vissim 9.0 software. The purpose of this research is to propose the implementation of an intelligent traffic signals to improve service levels and reduce traffic congestion. The process of building the model consists of four stages. First, it is the previous work, in which the field data collection was performed. The model was then constructed by Vissim 9.0 software. After, calibration and validation of the model was performed on both intersections based on psychophysical parameters to certify that the model results resemble the actual conditions of intersections. Finally, new future flows were incorporated into the model every 15 minutes which were simulated and evaluated with the NS obtained, incorporating the proposed improvement. Essentially service levels intersections improve, determining every 15 minutes during rush hour new signalized cycles optimized with Synchro 10.0 program applied to Vissim 9.0, from an NS E to D, It follows from decreasing lengths queues at all entrances and reducing travel delays, which were 14% at Av. Javier Prado -. Ca. Las Flores and 24% on Av. Javier Prado -. Ca. Las Palmeras. / Trabajo de investigación

Traditional intersections have always caused congestion, delay, and accidents. There are numerous geometric intersection designs that best fit each situation. This study performed an operational and safety comparison with unsignalized/signalized offset, Tintersections, a two-lane roundabout, and a modified roundabout to decrease the overall travel delay and increase the safety using a case study. Using data from a government source, all designs were tested in a calibrated micro simulation model and traffic signals were optimized using a signal optimization platform. Each design was tested with various balancing schemes, left turn percentages, and hourly volumes to determine the failure point. The unsignalized/signalized offset T-intersections, two-lane roundabout, and modified roundabout were compared by throughputs, travel delay, and travel time. After analysis, it was determined that the modified roundabout performed the best out of any design. All approaches had minimum travel delay while reducing the number of conflict points considerably with the modified roundabout. / Includes bibliography. / Thesis (M.S.)--Florida Atlantic University, 2014. / FAU Electronic Theses and Dissertations Collection

This study describes analytical model as one innovative way to simulate Light Rail Transit (LRT) operations and calculate vehicular, transit and person delays at LRT crossings through Microsoft Excel. Analytical model emulates LRT trajectories from field and use these trajectories to clearly define train and car phases through Visual Basic for Applications (VBA) logic, which is part of analytical model. Simulation of train trajectories and calculations of delays were done for different LRT strategies and estimated roadway condition, Testing and validation of analytical model were performed in one case study in Salt Lake City (UT). Results show that analytical model is capable of emulating LRT trajectories and estimating delay at isolated LRT crossing. However, analytical model is not capable of simulating different train strategies at two or more LRT crossings, at the same time. Finally, extracted strategy provides savings from $100.000 to $200.000 in study area, on annual basis for projected year. / by Nikola Mitrovic. / Thesis (M.S.C.S.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.