@inproceedings{3499, abstract = {We study infinite stochastic games played by n-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero-sum (the players’ goals are not necessarily conflicting), and undiscounted. We show that if each player has an upward-closed objective, then there exists an ε-Nash equilibrium in memoryless strategies, for every ε>0; and exact Nash equilibria need not exist. Upward-closure of an objective means that if a set Z of infinitely repeating states is winning, then all supersets of Z of infinitely repeating states are also winning. Memoryless strategies are strategies that are independent of history of plays and depend only on the current state. We also study the complexity of finding values (payoff profile) of an ε-Nash equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent games with upward-closed objectives for all players can be computed by computing ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives for all players and a polynomial procedure. As a consequence we establish that values of an ε-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME. }, author = {Chatterjee, Krishnendu}, booktitle = {Proceedings of the 20th international conference on Computer Science Logic}, isbn = {9783540454588}, issn = {1611-3349}, location = {Szeged, Hungary}, pages = {271 -- 286}, publisher = {Springer Nature}, title = {{Nash equilibrium for upward-closed objectives}}, doi = {10.1007/11874683_18}, volume = {4207}, 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{3894, abstract = {We study infinite stochastic games played by n-players on a finite graph with goals given by sets of infinite traces. The games are stochastic (each player simultaneously and independently chooses an action at each round, and the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero sum (the players' goals are not necessarily conflicting), and undiscounted. We show that if each player has a reachability objective, that is, if the goal for each player i is to visit some subset R-i of the states, then there exists an epsilon-Nash equilibrium in memoryless strategies, for every epsilon > 0. However, exact Nash equilibria need not exist. We study the complexity of finding such Nash equilibria, and show that the payoff of some epsilon-Nash equilibrium in memoryless strategies can be epsilon-approximated in NP. We study the important subclass of n-player turn-based probabilistic games, where at each state at most one player has a nontrivial choice of moves. For turn-based probabilistic games, we show the existence of epsilon-Nash equilibria in pure strategies for games where the objective of player i is a Borel set B-i of infinite traces. However, exact Nash equilibria may not exist. For the special case of omega-regular objectives, we show exact Nash equilibria exist, and can be computed in NP when the omega-regular objectives are expressed as parity objectives.}, author = {Chatterjee, Krishnendu and Majumdar, Ritankar and Jurdziński, Marcin}, booktitle = {18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL}, isbn = {9783540230243}, issn = {1611-3349}, location = {Karpacz, Poland}, pages = {26 -- 40}, publisher = {Springer Nature}, title = {{On Nash equilibria in stochastic games}}, doi = {10.1007/978-3-540-30124-0_6}, volume = {3210}, 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}, } @inproceedings{11804, abstract = {This paper shows how a general technique, called lock-step search, used in dynamic graph algorithms, can be used to improve the running time of two problems arising in program verification and communication protocol design. (1)We consider the nonemptiness problem for Streett automata: We are given a directed graph G = (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices, called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle (not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm that takes time 𝑂(𝑚min{𝑚𝑙𝑜𝑔𝑛,‾‾‾‾‾‾√𝑘,𝑛}+𝑏𝑚𝑖𝑛{𝑙𝑜𝑔𝑛,𝑘}). (2)In communication protocol pruning we are given a directed graph G = (V, E) with l special vertices. The problem is to efficiently maintain the strongly-connected components of the special vertices on a restricted set of edge deletions. Let m i be the number of edges in the strongly connected component of the ith special vertex. The previously best algorithm repeatedly recomputes the strongly-connected components which leads to a running time of O(Σ i m 2i). We present an algorithm with time 𝑂(𝑙√∑𝑖𝑚1.5𝑖).}, author = {Henzinger, Monika H and Telle, Jan Arne}, booktitle = {5th Scandinavian Workshop on Algorithm Theory}, isbn = {9783540614227}, issn = {1611-3349}, location = {Reykjavik, Iceland}, pages = {16–27}, publisher = {Springer Nature}, title = {{Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning}}, doi = {10.1007/3-540-61422-2_117}, volume = {1097}, year = {1996}, } @inproceedings{11910, abstract = {We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log3 n) per update, amortized over Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2 n). There exists a lower bound in the cell probe model for the time per operation of Ω(log n/ log log n) for this problem. Similarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.}, author = {Henzinger, Monika H and Thorup, Mikkel}, booktitle = {23rd International Colloquium on Automata, Languages, and Programming}, isbn = {9783540614401}, issn = {1611-3349}, location = {Paderborn, Germany}, pages = {290--299}, publisher = {Springer Nature}, title = {{Improved sampling with applications to dynamic graph algorithms}}, doi = {10.1007/3-540-61440-0_136}, volume = {1099}, year = {1996}, } @book{4612, editor = {Alur, Rajeev and Henzinger, Thomas A and Sontag, Eduardo D}, isbn = {978-3-540-61155-4}, issn = {0302-9743}, pages = {IX, 619}, publisher = {Springer}, title = {{Hybrid Systems III: Verification and Control}}, doi = {10.1007/BFb0020931}, volume = {1066}, year = {1996}, } @inproceedings{11805, abstract = {In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].}, author = {Henzinger, Monika H and Poutré, Han}, booktitle = {3rd Annual European Symposium on Algorithms}, isbn = {9783540603139}, issn = {1611-3349}, location = {Corfu, Greece}, pages = {171–184}, publisher = {Springer Nature}, title = {{Certificates and fast algorithms for biconnectivity in fully-dynamic graphs}}, doi = {10.1007/3-540-60313-1_142}, volume = {979}, year = {1995}, } @inproceedings{11806, abstract = {This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε).}, author = {Henzinger, Monika H}, booktitle = {22nd International Colloquium on Automata, Languages and Programming}, isbn = {9783540494256}, issn = {1611-3349}, location = {Szeged, Hungary}, pages = {280–291}, publisher = {Springer Nature}, title = {{Approximating minimum cuts under insertions}}, doi = {10.1007/3-540-60084-1_81}, volume = {944}, year = {1995}, }