@inproceedings{3880, abstract = {We consider imperfect-information parity games in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.}, author = {Berwanger, Dietmar and Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A and Raje, Sangram}, booktitle = {19th International Conference, CONCUR 2008}, issn = {1611-3349}, location = {Toronto, Canada}, pages = {325 -- 339}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Strategy construction for parity games with imperfect information}}, doi = {10.1007/978-3-540-85361-9}, volume = {5201}, year = {2008}, } @inproceedings{3879, abstract = {Quantitative generalizations of classical languages, which assign to each word a real number instead of a boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to define several natural classes of quantitative languages over finite and infinite words; in particular, the real value of an infinite run is computed as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We define the classical decision problems of automata theory (emptiness, universality, language inclusion, and language equivalence) in the quantitative setting and study their computational complexity. As the decidability of language inclusion remains open for some classes of weighted automata, we introduce a notion of quantitative simulation that is decidable and implies language inclusion. We also give a complete characterization of the expressive power of the various classes of weighted automata. In particular, we show that most classes of weighted automata cannot be determinized.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, booktitle = {22nd International Workshop on Computer Science Logic}, issn = {1611-3349}, location = {Bertinoro, Italy}, pages = {385 -- 400}, publisher = {Springer Nature}, title = {{Quantitative languages}}, doi = {10.1007/978-3-540-87531-4_28}, volume = {5213}, year = {2008}, } @inproceedings{3875, abstract = {We study the problem of model checking Interval-valued Discrete-time Markov Chains (IDTMC). IDTMCs are discrete-time finite Markov Chains for which the exact transition probabilities are riot known. Instead in IDTMCs, each transition is associated with an interval in which the actual transition probability must lie. We consider two semantic interpretations for the uncertainty in the transition probabilities of an IDTMC. In the first interpretation, we think of an IDTMC as representing a (possibly uncountable) family of (classical) discrete-time Markov Chains, where each member of the family is a Markov Chain whose transition probabilities lie within the interval range given in the IDTMC. We call this semantic interpretation Uncertain Markov Chains (UMC). In the second semantics for an IDTMC, which we call Interval Markov Decision Process (IMDP), we view the uncertainty as being resolved through non-determinism. In other words, each time a state is visited, we adversarially pick a transition distribution that respects the interval constraints, and take a probabilistic step according to the chosen distribution. We introduce a logic omega-PCTL that can express liveness, strong fairness, and omega-regular properties (such properties cannot be expressed in PCTL). We show that the omega-PCTL model checking problem for Uncertain Markov Chain semantics is decidable in PSPACE (same as the best known upper bound for PCTL) and for Interval Markov Decision Process semantics is decidable in coNP (improving the previous known PSPACE bound for PCTL). We also show that the qualitative fragment of the logic can lie solved in coNP for the UMC interpretation, and can be solved in polynomial time for a sub-class of UMCs. We also prove lower bounds for these model checking problems. We show that the model checking problem of IDTMCs with LTL formulas can be solved for both UMC and IMDP semantics by reduction to the model checking problem of IDTMC with omega-PcTL formulas.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Sen, Koushik}, booktitle = {Foundations of Software Science and Computational Structures - 11th International Conference}, issn = {1611-3349}, location = {Budapest, Hungary}, pages = {302 -- 317}, publisher = {Springer Nature}, title = {{Model-checking omega-regular properties of interval Markov chains}}, doi = {10.1007/978-3-540-78499-9_22}, volume = {4962}, year = {2008}, } @inproceedings{3873, abstract = {We study the controller synthesis problem under budget constraints. In this problem, there is a cost associated with making an observation, and a controller can make only a limited number of observations in each round so that the total cost of the observations does not exceed a given fixed budget. The controller must ensure some omega-regular requirement subject to the budget constraint. Budget constraints arise in designing and implementing controllers for resource-constrained embedded systems, where a controller may not have enough power, time, or bandwidth to obtain data from all sensors in each round. They lead to games of imperfect information, where the unknown information is not fixed a priori, but can vary from round to round, based on the choices made by the controller how to allocate its budget. We show that the budget-constrained synthesis problem for W-regular objectives is complete for exponential time. In addition to studying synthesis under a fixed budget constraint, we study the budget optimization problem, where given a plant, an objective, and observation costs, we have to find a controller that achieves the objective with minimal average accumulated cost (or minimal peak cost). We show that this problem is reducible to a game of imperfect information where the winning objective is a conjunction of an omega-regular condition and a long-run average condition (or a least max-cost condition), and this again leads to an exponential-time algorithm. Finally, we extend our results to games over infinite state spaces, and show that the budget-constrained synthesis problem is decidable for infinite state games with stable quotients of finite index. Consequently, the discrete time budget-constrained synthesis problem is decidable for rectangular hybrid automata.}, author = {Chatterjee, Krishnendu and Majumdar, Ritankar and Henzinger, Thomas A}, booktitle = {11th Workshop on Hybrid Systems: Computation and Control}, issn = {1611-3349}, location = {St. Louis, MO, United States}, pages = {72 -- 86}, publisher = {Springer Nature}, title = {{Controller synthesis with budget constraints}}, doi = {DOI: 10.1007/978-3-540-78929-1_6}, volume = {4981}, year = {2008}, } @inproceedings{3877, abstract = {The synthesis problem asks to construct a reactive finite-state system from an omega-regular specification. Initial specifications are often unrealizable, which means that there is no system that implements the specification. A common reason for unrealizability is that assumptions on the environment of the system are incomplete. We study the problem of correcting an unrealizable specification phi by computing an environment assumption psi such that the new specification psi -> phi is realizable. Our aim is to construct an assumption psi that constrains only the environment and is as weak as possible. We present a two-step algorithm for computing assumptions. The algorithm operates on the game graph that is used to answer the realizability question. First, we compute a safety assumption that removes a minimal set of environment edges from the graph. Second, we compute a liveness assumption that puts fairness conditions on some of the remaining environment edges. We show that the problem of finding a minimal set of fair edges is computationally hard, and we use probabilistic games to compute a locally minimal fairness assumption.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara}, booktitle = {19th International Conference on Concurrency Theory}, issn = {1611-3349}, location = {Toronto, Canada}, pages = {147 -- 161}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Environment assumptions for synthesis}}, doi = {10.1007/978-3-540-85361-9_14}, volume = {5201}, year = {2008}, } @inproceedings{3874, abstract = {We consider concurrent two-player timed automaton games with omega-regular objectives specified as parity conditions. These games offer an appropriate model for the synthesis of real-time controllers. Earlier works on timed games focused on pure strategies for each player. We study, for the first time, the use of randomized strategies in such games. While pure (i.e., nonrandomized) strategies in timed games require infinite memory for winning even with respect to reachability objectives, we show that randomized strategies can win with finite memory with respect to all parity objectives. Also, the synthesized randomized real-time controllers are much simpler in structure than the corresponding pure controllers, and therefore easier to implement. For safety objectives we prove the existence of pure finite-memory winning strategies. Finally, while randomization helps in simplifying the strategies required for winning timed parity games, we prove that randomization does not help in winning at more states.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak}, booktitle = {11th Workshop on Hybrid Systems: Computation and Control}, issn = {1611-3349}, location = {St. Louis, MO, United States}, pages = {87 -- 100}, publisher = {Springer Nature}, title = {{Trading infinite memory for uniform randomness in timed games}}, doi = {10.1007/978-3-540-78929-1_7}, volume = {4981}, year = {2008}, } @inproceedings{18320, abstract = {Presented here is the problem of recovering a dynamic image superimposed on a static background. Such a problem is ill-posed and may arise e.g. in imaging through semireflective media, in separation of an illumination image from a reflectance image, in imaging with diffraction phenomena, etc. In this work we study regularization of this problem in spirit of Total Variation and general sparsifying transformations.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Zibulevsky, Michael}, booktitle = {6th International Conference on Independent Component Analysis and Signal Separation}, isbn = {9783540326304}, issn = {1611-3349}, location = {Charleston, SC, United States}, pages = {934--940}, publisher = {Springer Nature}, title = {{On separation of semitransparent dynamic images from static background}}, doi = {10.1007/11679363_116}, volume = {3889}, year = {2006}, } @inproceedings{18321, abstract = {Recent studies on three-dimensional face recognition proposed to model facial expressions as isometries of the facial surface. Based on this model, expression-invariant signatures of the face were constructed by means of approximate isometric embedding into flat spaces. Here, we apply a new method for measuring isometry-invariant similarity between faces by embedding one facial surface into another. We demonstrate that our approach has several significant advantages, one of which is the ability to handle partially missing data. Promising face recognition results are obtained in numerical experiments even when the facial surfaces are severely occluded.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron}, booktitle = {9th European Conference on Computer Vision}, isbn = {9783540338369}, issn = {1611-3349}, location = {Graz, Austria}, publisher = {Springer Nature}, title = {{Robust expression-invariant face recognition from partially missing data}}, doi = {10.1007/11744078_31}, volume = {3953}, year = {2006}, } @inproceedings{18322, abstract = {A geometric framework for finding intrinsic correspondence between animated 3D faces is presented. We model facial expressions as isometries of the facial surface and find the correspondence between two faces as the minimum-distortion mapping. Generalized multidimensional scaling is used for this goal. We apply our approach to texture mapping onto 3D video, expression exaggeration and morphing between faces.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron}, booktitle = {4th International Conference on Articulated Motion and Deformable Objects}, isbn = {9783540360315}, issn = {1611-3349}, location = {Mallorca, Spain}, pages = {38--47}, publisher = {Springer Nature}, title = {{Facetoface: An isometric model for facial animation}}, doi = {10.1007/11789239_5}, volume = {4069}, year = {2006}, } @inproceedings{18323, abstract = {We present a theoretical and computational framework for matching of two-dimensional articulated shapes. Assuming that articulations can be modeled as near-isometries, we show an axiomatic construction of an articulation-invariant distance between shapes, formulated as a generalized multidimensional scaling (GMDS) problem and solved efficiently. Some numerical results demonstrating the accuracy of our method are presented.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Bruckstein, Alfred M. and Kimmel, Ron}, booktitle = {4th International Conference on Articulated Motion and Deformable Objects}, isbn = {9783540360315}, issn = {1611-3349}, location = {Mallorca, Spain}, pages = {48--57}, publisher = {Springer Nature}, title = {{Matching two-dimensional articulated shapes using generalized multidimensional scaling}}, doi = {10.1007/11789239_6}, volume = {4069}, year = {2006}, } @inproceedings{18319, abstract = {The problem of isometry-invariant representation and comparison of surfaces is of cardinal importance in pattern recognition applications dealing with deformable objects. Particularly, in three-dimensional face recognition treating facial expressions as isometries of the facial surface allows to perform robust recognition insensitive to expressions. Isometry-invariant representation of surfaces can be constructed by isometrically embedding them into some convenient space, and carrying out the comparison in that space. Presented here is a discussion on isometric embedding into S3, which appears to be superior over the previously used Euclidean space in sense of the representation accuracy.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron}, booktitle = {5th International Conference on Scale-Space Theories in Computer Vision}, isbn = {9783540255475}, issn = {1611-3349}, location = {Hofgeismar, Germany}, pages = {622--631}, publisher = {Springer Berlin Heidelberg}, title = {{Isometric embedding of facial surfaces into S3}}, doi = {10.1007/11408031_53}, volume = {3459}, year = {2005}, } @inproceedings{11800, abstract = {Web search engines have emerged as one of the central applications on the Internet. In fact, search has become one of the most important activities that people engage in on the the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition. The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploying the PageRank technology – an eigenvector-based analysis of the hyperlink structure – to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results.}, author = {Henzinger, Monika H}, booktitle = {31st International Colloquium on Automata, Languages and Programming}, issn = {1611-3349}, location = {Turku, Finland}, pages = {3}, publisher = {Springer Nature}, title = {{The past, present, and future of web search engines}}, doi = {10.1007/978-3-540-27836-8_2}, volume = {3142}, year = {2004}, } @inproceedings{11801, abstract = {Web search engines have emerged as one of the central applications on the internet. In fact, search has become one of the most important activities that people engage in on the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition. In this talk I will brief review the history of web search engines: The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploying the PageRank technology – an eigenvector-based analysis of the hyperlink structure- to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results. Google is powered by a large number of PCs. Using this infrastructure and striving to be as efficient as possible poses challenging systems problems but also various algorithmic challenges. I will discuss some of them in my talk.}, author = {Henzinger, Monika H}, booktitle = {2th Annual European Symposium on Algorithms}, isbn = { 3540230254}, issn = {1611-3349}, location = {Bergen, Norway}, pages = {3}, publisher = {Springer Nature}, title = {{Algorithmic aspects of web search engines}}, doi = {10.1007/978-3-540-30140-0_2}, volume = {3221}, year = {2004}, } @inproceedings{18331, abstract = {Recently, a 3D face recognition approach based on geometric invariant signatures, has been proposed. The key idea is a representation of the facial surface, invariant to isometric deformations, such as those resulting from facial expressions. One important stage in the construction of the geometric invariants involves in measuring geodesic distances on triangulated surfaces, which is carried out by the fast marching on triangulated domains algorithm. Proposed here is a method that uses only the metric tensor of the surface for geodesic distance computation. That is, the explicit integration of the surface in 3D from its gradients is not needed for the recognition task. It enables the use of simple and cost-efficient 3D acquisition techniques such as photometric stereo. Avoiding the explicit surface reconstruction stage saves computational time and reduces numerical errors.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Spira, Alon and Kimmel, Ron}, booktitle = {8th European Conference on Computer Vision}, isbn = {9783540219835}, issn = {1611-3349}, location = {Prageu, Czech Republic}, pages = {225–237}, publisher = {Springer Nature}, title = {{Face recognition from facial surface metric}}, doi = {10.1007/978-3-540-24671-8_18}, volume = {3022}, year = {2004}, } @inproceedings{18332, abstract = {Presented here is a generalization of the modified relative Newton method, recently proposed in [1] for quasi-maximum likelihood blind source separation. Special structure of the Hessian matrix allows to perform block-coordinate Newton descent, which significantly reduces the algorithm computational complexity and boosts its performance. Simulations based on artificial and real data show that the separation quality using the proposed algorithm outperforms other accepted blind source separation methods.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Zibulevsky, Michael}, booktitle = {5th International Conference on Independent Component Analysis and Blind Signal Separation}, isbn = {9783540230564}, issn = {1611-3349}, location = {Granada, Spain}, pages = {406–413}, publisher = {Springer Nature}, title = {{Blind source separation using the block-coordinate relative Newton method}}, doi = {10.1007/978-3-540-30110-3_52}, volume = {3195}, year = {2004}, } @inproceedings{18333, abstract = {The relative Newton algorithm, previously proposed for quasi maximum likelihood blind source separation and blind deconvolution of one-dimensional signals is generalized for blind deconvolution of images. Smooth approximation of the absolute value is used in modelling the log probability density function, which is suitable for sparse sources. We propose a method of sparsification, which allows blind deconvolution of sources with arbitrary distribution, and show how to find optimal sparsifying transformations by training.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Zibulevsky, Michael and Zeevi, Yehoshua Y.}, booktitle = {5th International Conference on Independent Component Analysis and Blind Signal Separation}, isbn = {9783540230564}, issn = {1611-3349}, location = {Granada, Spain}, pages = {500--507}, publisher = {Springer Nature}, title = {{Optimal sparse representations for blind deconvolution of images}}, doi = {10.1007/978-3-540-30110-3_64}, volume = {3195}, year = {2004}, } @inproceedings{18334, abstract = {We propose a relative optimization framework for quasi maximum likelihood blind deconvolution and the relative Newton method as its particular instance. Special Hessian structure allows its fast approximate construction and inversion with complexity comparable to that of gradient methods. The use of rational IIR restoration kernels provides a richer family of filters than the traditionally used FIR kernels. Smoothed absolute value and the smoothed deadzone functions allow accurate and robust deconvolution of super- and sub-Gaussian sources, respectively. Simulation results demonstrate the efficiency of the proposed methods.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Zibulevsky, Michael}, booktitle = {5th International Conference on Independent Component Analysis and Blind Signal Separation}, isbn = {9783540230564}, issn = {1611-3349}, location = {Granada, Spain}, pages = {554–561}, publisher = {Springer Nature}, title = {{Blind deconvolution using the relative Newton method}}, doi = {10.1007/978-3-540-30110-3_71}, volume = {3195}, year = {2004}, } @inproceedings{18324, abstract = {We present a novel 3D face recognition approach based on geometric invariants introduced by Elad and Kimmel. The key idea of the proposed algorithm is a representation of the facial surface, invariant to isometric deformations, such as those resulting from different expressions and postures of the face. The obtained geometric invariants allow mapping 2D facial texture images into special images that incorporate the 3D geometry of the face. These signature images are then decomposed into their principal components. The result is an efficient and accurate face recognition algorithm that is robust to facial expressions. We demonstrate the results of our method and compare it to existing 2D and 3D face recognition algorithms.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron}, booktitle = {4th International Conference on Audio- and Video-Based Biometric Person Authentication}, isbn = {9783540403029}, issn = {1611-3349}, location = {Guildford, United Kingdom}, pages = {62--70}, publisher = {Springer Nature}, title = {{Expression-invariant 3D face recognition}}, doi = {10.1007/3-540-44887-x_8}, volume = {2688}, year = {2003}, } @inproceedings{11802, abstract = {In this paper we survey algorithmic aspects of Web information retrieval. As an example, we discuss ranking of search engine results using connectivity analysis.}, author = {Henzinger, Monika H}, booktitle = {8th Annual European Symposium on Algorithms}, isbn = {9783540410041}, issn = {1611-3349}, location = {Saarbrücken, Germany}, pages = {1–8}, publisher = {Springer Nature}, title = {{Web information retrieval - an algorithmic perspective}}, doi = {10.1007/3-540-45253-2_1}, volume = {1879}, year = {2000}, } @inproceedings{11803, abstract = {We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.}, author = {Henzinger, Monika H and King, Valerie}, booktitle = {24th International Colloquium on Automata, Languages and Programming}, isbn = {9783540631651}, issn = {1611-3349}, location = {Bologna, Italy}, pages = {594–604}, publisher = {Springer Nature}, title = {{Maintaining minimum spanning trees in dynamic graphs}}, doi = {10.1007/3-540-63165-8_214}, volume = {1256}, year = {1997}, }