Fast. Cheap. Reliable. Choose two.
Ana Paula Tomás, DCC & CMUP
27th May 2015, 14:00
DCC Amphitheater 2 (FC6-029)

An old engineering slogan says, “Fast. Cheap. Reliable. Choose two.” Similarly, unless P = NP, we can’t simultaneously have algorithms that (1) find optimal solutions (2) in polynomial time (3) for any instance. At least one of these requirements must be relaxed in any approach to dealing with an NP-hard optimisation problem [Williamson & Shmoys, 2010]. What about polynomial-time approximation algorithms, which return near-optimal (or good enough) solutions? How close to optimum can we get in polynomial time?
In this talk we will see some inapproximability results for art gallery problems in polygons.

Heuristics for Packing Semifluids
João Pedro Pedroso, INESC TEC
13th May 2015, 14:00
DCC Amphitheater 2 (FC6-029)

Physical properties of materials are seldom studied in the context of packing problems. In this work we study the behavior of semifluids: materials with particular characteristics, that share properties both with solids and with fluids. We describe the importance of some specific semifluids in an industrial context, and propose methods for tackling the problem of packing them, taking into account several practical requirements and physical constraints.

Discovering Subgraph Patterns in Complex Networks

Pedro Ribeiro, INESC TEC/CRACS
29th April 2015, 16:00
DCC Amphitheater 2 (FC6-029)

Complex networks are ubiquitous in real-world systems. One way to understand their design principles is look at how they are organized at the subgraph level, discovering small characteristic building blocks. In this talk I will describe two concepts geared around this idea, namely network motifs and graphlets. At the core of these methodologies lies the ability to search and count subgraphs. This is a computationally hard problem and I will talk about the state of the art for this task, focusing on the g-trie data structure, designed to efficiently represent a collection of graphs and to search for them as induced subgraphs of another larger graph. I will explain how it takes advantage of common substructure and how symmetry breaking conditions can be used to avoid redundant computations. I will explain its general applicability, showcasing how it would work for undirected, directed and colored graphs. I will also briefly discuss sampling and parallel versions of g-trie based methods and I will show some empirical results on a set of complex networks from various domains. Finally, I will give examples of applications and I will talk about possible future work on this area.

Where do Ad-Hoc networks go… Somewhere?

Pedro Brandão, Instituto de Telecomunicações (IT)
25th March 2015, 14:00
DCC Amphitheater 2 (FC6-029)

This talk will discuss our current work on using IEEE 802.11 Ad-Hoc mode to enable connectivity between wireless nodes without infrastructure access. These settings can be relevant in no connectivity scenarios such as first responders in disasters or remote locations, or casual/ad-hoc gathering of groups.
I will introduce some of the details behind ad-hoc mode, then describe our initial work with Android smartphones (and its seemingly dying support). The motivating scenario is the first responder unit. I will go into possible overlay technologies that have the same aims (mostly for casual users) and finish with our current work using Raspberry Pis.
This is ongoing work, with mostly network systems discussions, dwelling in throughput, delay evaluation, hardware/software fights among integration and deployment guerilla.

Towards Out-of-the-Box Programming of Wireless Sensor-Actuator Networks

Luís Lopes, INESC TEC/CRACS
11th March 2015, 14:00
DCC Amphitheater 2 (FC6-029)

We address the problem of providing users, namely non specialists, with out-of-the-box, programmable, Wireless Sensor-Actuator Networks (WSN). The idea is that users get a package containing a gateway and an undetermined number of nodes, pre-configured to work as a self-organized wireless mesh. Each node comes with two pre-installed components: a small operating system and a virtual machine. The user can then use a simple, domain-specific, programming language to implement periodic tasks that are compiled into bytecode, and can be sent to the nodes for execution. At the nodes, the small operating system manages a task table and schedules non-preemptive tasks for execution using the virtual machine. No subtle hardware or software configuration is required from the user as these details are abstracted away by the virtual machine. We have developed a full specification for a data-layer that follows the aforementioned guidelines and implemented a complete prototype. The latter was then integrated into an existing publish/subscribe middleware that feeds web-clients with data streams from the WSN. The memory and processing footprint of the operating system and virtual machine in the nodes is modest even without optimization and these modules can be seamlessly ported to other microcontrollers and/or other combinations of sensors/actuators.

The automatic creation of a look-a-like avatar

Verónica Orvalho, IT Porto / PIC
26th November 2014, 14:00
DCC Amphitheater 2 (FC6-029)

Creating a 3D avatar that looks like a specific person is time-consuming, requires expert artists, expensive equipment and a complex pipeline. In this talk I will walk you through the avatar animation pipeline created at PIC (Porto Interactive Center, www.portointeractivecenter.org) for the VERE (Virtual Embodiment and Robotic re-Embodiment, http://www.vereproject.eu/) European Project. This new pipeline does not require the user to have artistic knowledge, uses regular cameras to create the 3D avatar and a webcam to generate the animation.

Size matters, but let’s compare it with the average value!

Rogério Reis, CMUP
18th June 2014, 14:00
DCC Amphitheater 2 (FC6-029)

The average descriptional complexity of an operation is, for almost all applications, much more significant than its worst case counterpart. But the evaluation of this average value used to be only feasible by experimental approximation. Analytic Combinatorics offers a new approach to this problem, that already delivered exact results for a non trivial number of instances, and can be successfully extended to a quite broad range of areas.

2 in 1 for Data Analysis [slides]

Luis Torgo, LIAAD/INESC TEC
4th June 2014, 14:00
DCC Room S2 (FC6-140)

People working on data analysis frequently follow a work-flow that involves the following main steps: (i) get the data into your favorite data analysis tool; (ii) perform some data analysis steps; (iii) build a report and/or presentation on the obtained results. The third step is typically carried out using a separate tool (e.g. word processor or presentation software) and this involves lots of copy-pasting and manual labor from the analysis tool to the reporting tool. Moreover, all process is frequently repeated many times as a result of feedback based on the report. All this is seriously prone to error and being manually intensive, very hard to automate or replicate (for instance when you try to pass your work to others). These and other problems lead to the concept of dynamic documents, for which the R programming environment provides very interesting and elegant solutions that lead to a serious boost in productivity and correctness of all this process. In a nut shell the idea of dynamic documents is that of integrating the analysis and the reporting in a single document and let R produce automatically the report from this document, i.e. a 2 in 1 process. This short and practical presentation will briefly introduce you to this process and will provide simple illustrations of its advantages.

Authenticus – Authenticating scientific publications authored by researchers from Portuguese institutions

Fernando Silva, CRACS
21st May 2014, 14:00
DCC Amphitheater 2 (FC6-029)

Authenticus is a framework aiming to support the creation of institutional databases of scientific publications automatically aggregated from multiple indexing sources such as ISI Web-of-Knowledge, Scopus, DBLP, and ORCID. Currently, we have created a national database of publications, with over 240,000 publication records. Authenticus automatically associates publications to known researchers and institutions. These associations can later be validated by the owner researchers, thus improving data trustability, something critical in the development of useful and reliable bibliometric indicators for research performance assessment.

For this presentation, we focus on the architecture of Authenticus, in particular in the author name disambiguation algorithm, action-center and task-scheduler. Author identification in publications is full of uncertainty and thus correctly matching an author name with the name of a known researcher requires specialized matching algorithms and heuristic procedures on many validation parameters to successfully disambiguate potential matches.  The action-center is the heart of our model controller, responsible for abstracting data-access, providing developers with a flexible query-builder, ensuring logging of events and errors for future recovery purposes, and monitoring database transactions. The task-scheduler is a component used extensively both to coordinate the execution of many user generated operations over the database, e.g. confirming a set of selected publications, as well as to control the execution of scheduled batch operations, e.g. the weekly updates of publications that appeared in ISI or Scopus. Other functionalities are also highlighted, namely publications redundancy verification, export/print functionalities, and bibliometrics indicators. We conclude with a demo of Authenticus.

Pythondo: a web system for automatic feedback of programming assignments [slides]

Pedro Vasconcelos, LIACC
7th May 2014, 14:00
DCC Amphitheater 2 (FC6-029)

“Pythondo'” is a web-based application for giving automatic feedback of programming assignments in Python. It was developed to help teaching programming to first-year non-CS students of the FCUP.
In this talk I will explain the design principles of the “Pythondo” system and some aspects of its implementation using the Snap Haskell web framework.
Keywords: teaching programming, Python, Haskell, web frameworks.

Augmented reality driving supported by vehicular ad hoc networking

Michel Ferreira, Instituto de Telecomunicações (IT)
23rd April 2014, 14:00
DCC Amphitheater 2 (FC6-029)

The confined space of a car and the configuration of its controls and displays towards the driver, offer significant advantages for Augmented Reality (AR) systems in terms of the immersion level provided to the user. In addition, the inherent mobility and virtually unlimited power autonomy transform cars into perfect mobile computing platforms. However, the limited network connectivity that is currently available in automobiles leads to the design of Advanced Driver Assistance Systems (ADAS) that create AR objects based only on the information generated by on-board sensors, stored maps and databases, and eventually high-latency online content for Internet-enabled vehicles. By combining the new paradigm of Vehicular Ad Hoc Networking (VANET) with AR human machine interfaces, we show that it is possible to design novel cooperative ADAS, that base the creation of AR content on the information collected from neighbouring vehicles or roadside infrastructures. We provide concrete examples and prototype implementations of both acoustic and visual AR systems that can significantly improve the driving experience.

Multi-Relational Learning with applications to Health [slides]

Inês Dutra, Center for Research in Advanced Computer Systems (CRACS)
09th April 2014, 14:00
DCC Amphitheater 2 (FC6-029)

Image-guided percutaneous core needle biopsy is the standard of care for the diagnosis of a suspicious finding in the breast. Unfortunately, the assessment of malignancy risk following breast core biopsy is imperfect and biopsies can be “non-definitive” in 5-15% of cases. This category includes discordant biopsies, high risk lesions (atypical ductal hyperplasia, lobular carcinoma in situ, radial scar, etc.), and insufficient sampling. A non-definitive result means the chance of malignancy remains high due to possible sampling error (i.e. obtained biopsy is not representative of the suspicious finding), for which surgical excisional biopsy is performed. Image-guided breast core biopsies may therefore result in missed breast cancers (false negatives) or unnecessary surgery (false positives).
Our goal is to predict upgrade prospectively and avoid surgery in women who do not have breast cancer. Our results, some of which trended toward significance, show evidence that inductive logic programming may produce better results for this task than traditional propositional algorithms with default parameters. Moreover, we show that adding knowledge from our physicians into the learning process may improve the performance of the learned classifier trained only on data.

Towards Declarative Information Systems

António Porto, Laboratório de Inteligência Artificial e Ciência de Computadores (LIACC)
26th March 2014, 14:00
DCC Amphitheater 2 (FC6-029)

It is still a challenge to produce software systems that are truly effective, reliable and evolutive, especially organisational information systems. This talk is a status survey of a long-going project to provide answers to the challenge by leveraging declarative programming techniques and methodologies, spreading across three major layers:

• Cube – compositional unification-based engine – A structural logic programming platform that is an alternative to Prolog, with simple compositional semantics. A fully functional professional-grade implementation was made, with useful libraries and debugging facilities.
• NAF – natural attributive framework – A high-level solution for database management and interaction. Based on attributive modelling of concepts and on principles of natural language, it encompasses a modular scheme description language (NACS), a language for interaction with databases (NADI), and tools for database management.
• Compass –  concept-oriented modular and parametric architecture for service systems – A compositional architecture for building Web systems, implemented in Cube and using NAF; it provides a development environment and methodologies for rapid prototyping of organisational information systems.

DigiScope – Six years of mHealth experiences on cardiac auscultation

Miguel Coimbra, Instituto de Telecomunicações (IT)
12th March 2014, 14:00
DCC Amphitheatre 2 (FC6-029)

Auscultation is both an inexpensive pathology screening mechanism and a hard skill to master. The DigiScope research line has explored for the last six years how digital stethoscopes can help this process either via training, tele-medicine or computer-assisted decision approaches. In this talk we will understand how an initial research idea has evolved into a technology that has been licensed to a spin-off company of the University of Porto and has already integrated award-winning medical initiatives.