9 Search Results for "Mika, Peter"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.64
On the Communication Complexity of Finding a King in a Tournament

Authors: Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: - We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS'91, Göös, Pitassi, Watson, SICOMP'18] imply a bound of Θ̃(log² n) for finding a source (if it exists, or outputting that there is no source) in a tournament. - The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ̃(√n). - The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ̃(n) and Θ̃(√n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP'03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.
Cite as

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Communication Complexity of Finding a King in a Tournament. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 64:1-64:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.APPROX/RANDOM.2024.64,
  author =	{Mande, Nikhil S. and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Communication Complexity of Finding a King in a Tournament}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{64:1--64:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  URN =		{urn:nbn:de:0030-drops-210571},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  annote =	{Keywords: Communication complexity, tournaments, query complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.27
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds Through Circuits and Degree

Authors: Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche, and Luc Nicolas Spachmann

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We initiate an in-depth proof-complexity analysis of polynomial calculus (𝒬-PC) for Quantified Boolean Formulas (QBF). In the course of this we establish a tight proof-size characterisation of 𝒬-PC in terms of a suitable circuit model (polynomial decision lists). Using this correspondence we show a size-degree relation for 𝒬-PC, similar in spirit, yet different from the classic size-degree formula for propositional PC by Impagliazzo, Pudlák and Sgall (1999). We use the circuit characterisation together with the size-degree relation to obtain various new lower bounds on proof size in 𝒬-PC. This leads to incomparability results for 𝒬-PC systems over different fields.
Cite as

Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche, and Luc Nicolas Spachmann. Polynomial Calculus for Quantified Boolean Logic: Lower Bounds Through Circuits and Degree. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beyersdorff_et_al:LIPIcs.MFCS.2024.27,
  author =	{Beyersdorff, Olaf and Hoffmann, Tim and Kasche, Kaspar and Spachmann, Luc Nicolas},
  title =	{{Polynomial Calculus for Quantified Boolean Logic: Lower Bounds Through Circuits and Degree}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.27},
  URN =		{urn:nbn:de:0030-drops-205834},
  doi =		{10.4230/LIPIcs.MFCS.2024.27},
  annote =	{Keywords: proof complexity, QBF, polynomial calculus, circuits, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.15
Quantum Automating TC⁰-Frege Is LWE-Hard

Authors: Noel Arteche, Gaia Carenini, and Matthew Gray

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate TC⁰-Frege. This extends the line of results of Krajíček and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (Computational Complexity, 2004), who showed that Extended Frege, TC⁰-Frege and AC⁰-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.
Cite as

Noel Arteche, Gaia Carenini, and Matthew Gray. Quantum Automating TC⁰-Frege Is LWE-Hard. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arteche_et_al:LIPIcs.CCC.2024.15,
  author =	{Arteche, Noel and Carenini, Gaia and Gray, Matthew},
  title =	{{Quantum Automating TC⁰-Frege Is LWE-Hard}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{15:1--15:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.15},
  URN =		{urn:nbn:de:0030-drops-204117},
  doi =		{10.4230/LIPIcs.CCC.2024.15},
  annote =	{Keywords: automatability, post-quantum cryptography, feasible interpolation}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.145
The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters

Authors: George Kenison

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, ⟨u_n⟩_{n=0}^∞ is hypergeometric if it satisfies a first-order linear recurrence of the form p(n)u_{n+1} = q(n)u_n with polynomial coefficients p,q ∈ ℤ[x] and u₀ ∈ ℚ. In this paper, we consider the Threshold Problem for hypergeometric sequences: given a hypergeometric sequence ⟨u_n⟩_{n=0}^∞ and a threshold t ∈ ℚ, determine whether u_n ≥ t for each n ∈ ℕ₀. We establish decidability for the Threshold Problem under the assumption that the coefficients p and q are monic polynomials whose roots lie in an imaginary quadratic extension of ℚ. We also establish conditional decidability results; for example, under the assumption that the coefficients p and q are monic polynomials whose roots lie in any number of quadratic extensions of ℚ, the Threshold Problem is decidable subject to the truth of Schanuel’s conjecture. Finally, we show how our approach both recovers and extends some of the recent decidability results on the Membership Problem for hypergeometric sequences with quadratic parameters.
Cite as

George Kenison. The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 145:1-145:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kenison:LIPIcs.ICALP.2024.145,
  author =	{Kenison, George},
  title =	{{The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{145:1--145:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.145},
  URN =		{urn:nbn:de:0030-drops-202882},
  doi =		{10.4230/LIPIcs.ICALP.2024.145},
  annote =	{Keywords: Threshold Problem, Membership Problem, Hypergeometric Sequences}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.147
Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games

Authors: Bruno Loff and Mateusz Skomra

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We devise a policy-iteration algorithm for deterministic two-player discounted and mean-payoff games, that runs in polynomial time with high probability, on any input where each payoff is chosen independently from a sufficiently random distribution and the underlying graph of the game is ergodic. This includes the case where an arbitrary set of payoffs has been perturbed by a Gaussian, showing for the first time that deterministic two-player games can be solved efficiently, in the sense of smoothed analysis. More generally, we devise a condition number for deterministic discounted and mean-payoff games played on ergodic graphs, and show that our algorithm runs in time polynomial in this condition number. Our result confirms a previous conjecture of Boros et al., which was claimed as a theorem [Boros et al., 2011] and later retracted [Boros et al., 2018]. It stands in contrast with a recent counter-example by Christ and Yannakakis [Christ and Yannakakis, 2023], showing that Howard’s policy-iteration algorithm does not run in smoothed polynomial time on stochastic single-player mean-payoff games. Our approach is inspired by the analysis of random optimal assignment instances by Frieze and Sorkin [Frieze and Sorkin, 2007], and the analysis of bias-induced policies for mean-payoff games by Akian, Gaubert and Hochart [Akian et al., 2018].
Cite as

Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147,
  author =	{Loff, Bruno and Skomra, Mateusz},
  title =	{{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{147:1--147:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.147},
  URN =		{urn:nbn:de:0030-drops-202908},
  doi =		{10.4230/LIPIcs.ICALP.2024.147},
  annote =	{Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.12
From Proof Complexity to Circuit Complexity via Interactive Protocols

Authors: Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Folklore in complexity theory suspects that circuit lower bounds against NC¹ or P/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishing such a connection formally, however, is already daunting, as it would imply the breakthrough separation NEXP ⊈ P/poly, as recently observed by Pich and Santhanam [Pich and Santhanam, 2023]. We show such a connection conditionally for the Implicit Extended Frege proof system (iEF) introduced by Krajíček [Krajíček, 2004], capable of formalizing most of contemporary complexity theory. In particular, we show that if iEF proves efficiently the standard derandomization assumption that a concrete Boolean function is hard on average for subexponential-size circuits, then any superpolynomial lower bound on the length of iEF proofs implies #P ⊈ FP/poly (which would in turn imply, for example, PSPACE ⊈ P/poly). Our proof exploits the formalization inside iEF of the soundness of the sum-check protocol of Lund, Fortnow, Karloff, and Nisan [Lund et al., 1992]. This has consequences for the self-provability of circuit upper bounds in iEF. Interestingly, further improving our result seems to require progress in constructing interactive proof systems with more efficient provers.
Cite as

Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arteche_et_al:LIPIcs.ICALP.2024.12,
  author =	{Arteche, Noel and Khaniki, Erfan and Pich, J\'{a}n and Santhanam, Rahul},
  title =	{{From Proof Complexity to Circuit Complexity via Interactive Protocols}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.12},
  URN =		{urn:nbn:de:0030-drops-201557},
  doi =		{10.4230/LIPIcs.ICALP.2024.12},
  annote =	{Keywords: proof complexity, circuit complexity, interactive protocols}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.70
Acceptance Ambiguity for Quantum Automata

Authors: Paul C. Bell and Mika Hirvensalo

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We consider notions of freeness and ambiguity for the acceptance probability of Moore-Crutchfield Measure Once Quantum Finite Automata (MO-QFA). We study the distribution of acceptance probabilities of such MO-QFA, which is partly motivated by similar freeness problems for matrix semigroups and other computational models. We show that determining if the acceptance probabilities of all possible input words are unique is undecidable for 32 state MO-QFA, even when all unitary matrices and the projection matrix are rational and the initial configuration is defined over real algebraic numbers. We utilize properties of the skew field of quaternions, free rotation groups, representations of tuples of rationals as a linear sum of radicals and a reduction of the mixed modification Post’s correspondence problem.
Cite as

Paul C. Bell and Mika Hirvensalo. Acceptance Ambiguity for Quantum Automata. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bell_et_al:LIPIcs.MFCS.2019.70,
  author =	{Bell, Paul C. and Hirvensalo, Mika},
  title =	{{Acceptance Ambiguity for Quantum Automata}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.70},
  URN =		{urn:nbn:de:0030-drops-110149},
  doi =		{10.4230/LIPIcs.MFCS.2019.70},
  annote =	{Keywords: Quantum finite automata, matrix freeness, undecidability, Post’s correspondence problem, quaternions}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2017.19
Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Authors: Mikaël Mayer, Jad Hamza, and Viktor Kuncak

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute to foundations of such techniques and present a complete algorithm for synthesis of a class of recursive functions defined by structural recursion over a given algebraic data type definition. The functions we consider map an algebraic data type to a string; they are useful for, e.g., pretty printing and serialization of programs and data. We formalize our problem as learning deterministic sequential top-down tree-to-string transducers with a single state (1STS). The first problem we consider is learning a tree-to-string transducer from any set of input/output examples provided by the user. We show that, given a set of input/output examples, checking whether there exists a 1STS consistent with these examples is NP-complete in general. In contrast, the problem can be solved in polynomial time under a (practically useful) closure condition that each subtree of a tree in the input/output example set is also part of the input/output examples. Because coming up with relevant input/output examples may be difficult for the user while creating hard constraint problems for the synthesizer, we also study a more automated active learning scenario in which the algorithm chooses the inputs for which the user provides the outputs. Our algorithm asks a worst-case linear number of queries as a function of the size of the algebraic data type definition to determine a unique transducer. To construct our algorithms we present two new results on formal languages. First, we define a class of word equations, called sequential word equations, for which we prove that satisfiability can be solved in deterministic polynomial time. This is in contrast to the general word equations for which the best known complexity upper bound is in linear space. Second, we close a long-standing open problem about the asymptotic size of test sets for context-free languages. A test set of a language of words L is a subset T of L such that any two word homomorphisms equivalent on T are also equivalent on L. We prove that it is possible to build test sets of cubic size for context-free languages, matching for the first time the lower bound found 20 years ago.
Cite as

Mikaël Mayer, Jad Hamza, and Viktor Kuncak. Proactive Synthesis of Recursive Tree-to-String Functions from Examples. In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 19:1-19:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mayer_et_al:LIPIcs.ECOOP.2017.19,
  author =	{Mayer, Mika\"{e}l and Hamza, Jad and Kuncak, Viktor},
  title =	{{Proactive Synthesis of Recursive Tree-to-String Functions from Examples}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{19:1--19:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.19},
  URN =		{urn:nbn:de:0030-drops-72575},
  doi =		{10.4230/LIPIcs.ECOOP.2017.19},
  annote =	{Keywords: programming by example, active learning, program synthesis}
}
Document
DOI: 10.4230/DagSemProc.08391.3
08391 Group Summary – Mining for Social Serendipity

Authors: Alexandre Passant, Ian Mulvany, Peter Mika, Nicolas Maisonneuve, Alexander Löser, Ciro Cattuto, Christian Bizer, Christian Bauckhage, and Harith Alani

Published in: Dagstuhl Seminar Proceedings, Volume 8391, Social Web Communities (2008)

Abstract
A common social problem at an event in which people do not personally know all of the other participants is the natural tendency for cliques to form and for discussions to mainly happen between people who already know each other. This limits the possibility for people to make interesting new acquaintances and acts as a retarding force in the creation of new links in the social web. Encouraging users to socialize with people they don't know by revealing to them hidden surprising links could help to improve the diversity of interactions at an event. The goal of this paper is to propose a method for detecting extit{"surprising"} relationships between people attending an event. By extit{"surprising"} relationship we mean those relationships that are not known a-priori, and that imply shared information not directly related with the local context of the event (location, interests, contacts) at which the meeting takes place. To demonstrate and test our concept we used the Flickr community. We focused on a community of users associated with a social event (a computer science conference) and represented in Flickr by means of a photo pool devoted to the event. We use Flickr metadata (tags) to mine for user similarity not related to the context of the event, as represented in the corresponding Flickr group. For example, we look for two group members who have been in the same highly specific place (identified by means of geo-tagged photos), but are not friends of each other and share no other common interests or, social neighborhood.
Cite as

Alexandre Passant, Ian Mulvany, Peter Mika, Nicolas Maisonneuve, Alexander Löser, Ciro Cattuto, Christian Bizer, Christian Bauckhage, and Harith Alani. 08391 Group Summary – Mining for Social Serendipity. In Social Web Communities. Dagstuhl Seminar Proceedings, Volume 8391, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{passant_et_al:DagSemProc.08391.3,
  author =	{Passant, Alexandre and Mulvany, Ian and Mika, Peter and Maisonneuve, Nicolas and L\"{o}ser, Alexander and Cattuto, Ciro and Bizer, Christian and Bauckhage, Christian and Alani, Harith},
  title =	{{08391 Group Summary – Mining for Social Serendipity}},
  booktitle =	{Social Web Communities},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8391},
  editor =	{Harith Alani and Steffen Staab and Gerd Stumme},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08391.3},
  URN =		{urn:nbn:de:0030-drops-17910},
  doi =		{10.4230/DagSemProc.08391.3},
  annote =	{Keywords: Serendipity, online activity, context, ubiquitous computing}
}
  • Refine by Author
  • 2 Arteche, Noel
  • 1 Alani, Harith
  • 1 Bauckhage, Christian
  • 1 Bell, Paul C.
  • 1 Beyersdorff, Olaf
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Proof complexity
  • 2 Theory of computation → Quantum complexity theory
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Symbolic and algebraic algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 proof complexity
  • 1 Communication complexity
  • 1 Hypergeometric Sequences
  • 1 Mean-payoff games
  • 1 Membership Problem
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 6 2024
  • 1 2008
  • 1 2017
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact