Search results for "SOFC"
showing 10 items of 660 documents
Parameterized Quantum Query Complexity of Graph Collision
2013
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ qu…
Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
2018
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the best known deterministic algorithm is $O(n+m)$, where $n$ is the number of vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge; $m$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non…
Software startup education: gamifying growth hacking
2021
Startups seek to create highly scalable business models. For startups, growth is thus vital. Growth hacking is a marketing strategy advocated by various startup practitioner experts. It focuses on using low cost practices while utilizing existing platforms in creative ways to gain more users for the service. Though topics related to growth hacking such as marketing on a general level have been extensively studied in the past, growth hacking as a practitioner-born topic has not seen much interest among the academia. To both spark interest in growth hacking, and to facilitate teaching growth hacking in the academia, we present two board games intended to serve as an engaging introduction to g…
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness
2016
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
Governance of Ethical and Trustworthy Al Systems: Research Gaps in the ECCOLA Method
2021
Advances in machine learning (ML) technologies have greatly improved Artificial Intelligence (AI) systems. As a result, AI systems have become ubiquitous, with their application prevalent in virtually all sectors. However, AI systems have prompted ethical concerns, especially as their usage crosses boundaries in sensitive areas such as healthcare, transportation, and security. As a result, users are calling for better AI governance practices in ethical AI systems. Therefore, AI development methods are encouraged to foster these practices. This research analyzes the ECCOLA method for developing ethical and trustworthy AI systems to determine if it enables AI governance in development process…
A fully adaptive wavelet algorithm for parabolic partial differential equations
2001
We present a fully adaptive numerical scheme for the resolution of parabolic equations. It is based on wavelet approximations of functions and operators. Following the numerical analysis in the case of linear equations, we derive a numerical algorithm essentially based on convolution operators that can be efficiently implemented as soon as a natural condition on the space of approximation is satisfied. The algorithm is extended to semi-linear equations with time dependent (adapted) spaces of approximation. Numerical experiments deal with the heat equation as well as the Burgers equation.
Issues of Ethics and Methods in Studying Social Media
2016
The Editorial raises some challenging ethical and methodological aspects of Internet based research (such as protection of informational privacy, informed consent, general ethical guidelines vs case-based approach), which are further discussed in the five articles of this special issue.
Editorial: Issues of Ethics and Methods in Studying Social Media
2016
The Editorial raises some challenging ethical and methodological aspects of Internet based research (such as protection of informational privacy, informed consent, general ethical guidelines vs case-based approach), which are further discussed in the five articles of this special issue. nonPeerReviewed
An efficient algorithm for stopping on a sink in a directed graph
2013
Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.