@inproceedings{3878, abstract = {We study the problem of generating a test sequence that achieves maximal coverage for a reactive system under test. We formulate the problem as a repeated game between the tester and the system, where the system state space is partitioned according to some coverage criterion and the objective of the tester is to maximize the set of partitions (or coverage goals) visited during the game. We show the complexity of the maximal coverage problem for non-deterministic systems is PSPACE-complete, but is NP-complete for deterministic systems. For the special case of non-deterministic systems with a re-initializing “reset” action, which represent running a new test input on a re-initialized system, we show that the complexity is coNP-complete. Our proof technique for reset games uses randomized testing strategies that circumvent the exponentially large memory requirement of deterministic testing strategies.}, author = {Chatterjee, Krishnendu and De Alfaro, Luca and Majumdar, Ritankar}, booktitle = {6th Asian Symposium on Programming Language and Systems}, issn = {1611-3349}, location = {Bangalore, India}, pages = {91 -- 106}, publisher = {Springer Nature}, title = {{The complexity of coverage}}, doi = {10.1007/978-3-540-89330-1_7}, volume = {5356}, 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{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{3876, abstract = {We consider two-player games played in real time on game structures with clocks and parity objectives. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., nonconcurrent) finite-state (i.e., untimed) parity games. The states of the resulting game are pairs of clock regions of the original game. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust strategies. Using a limit-robust strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak}, booktitle = {Proceedings of the 6th international conference on Formal Modeling and Analysis of Timed Systems}, isbn = {9783540857778}, issn = {1611-3349}, location = {Saint Malo, France}, pages = {124 -- 140}, publisher = {Springer Nature}, title = {{Timed parity games: complexity and robustness}}, doi = {10.1007/978-3-540-85778-5_10}, volume = {5215}, 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{4578, abstract = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Blast is based on lazy predicate abstraction driven by interpolation-based predicate discovery. In this paper, we present the Blast specification language. The language specifies program properties at two levels of precision. At the lower level, monitor automata are used to specify temporal safety properties of program executions (traces). At the higher level, relational reachability queries over program locations are used to combine lower-level trace properties. The two-level specification language can be used to break down a verification task into several independent calls of the model-checking engine. In this way, each call to the model checker may have to analyze only part of the program, or part of the specification, and may thus succeed in a reduction of the number of predicates needed for the analysis. In addition, the two-level specification language provides a means for structuring and maintaining specifications. }, author = {Beyer, Dirk and Chlipala, Adam and Henzinger, Thomas A and Jhala, Ranjit and Majumdar, Ritankar}, isbn = {9783540227915}, issn = {0302-9743}, location = {Verona, Italy}, pages = {2 -- 18}, publisher = {Springer}, title = {{The BLAST query language for software verification}}, doi = {10.1007/978-3-540-27864-1_2}, volume = {3148}, 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{18335, abstract = {Blind deconvolution is considered as a problem of quasi maximum likelihood (QML) estimation of the restoration kernel. Simple closed-form expressions for the asymptotic estimation error are derived. The asymptotic performance bounds coincide with the Cramér-Rao bounds, when the true ML estimator is used. Conditions for asymptotic stability of the QML estimator are derived. Special cases when the estimator is super-efficient are discussed.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Zibulevsky, Michael and Zeevi, Yehoshua Y.}, booktitle = {Proceedings of the 5th International Conference on Independent Component Analysis and Blind Signal Separation}, isbn = {9783540230564}, issn = {0302-9743}, location = {Granada, Spain}, pages = {677–684}, publisher = {Springer Nature}, title = {{QML blind deconvolution: Asymptotic analysis}}, doi = {10.1007/978-3-540-30110-3_86}, 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}, }