Scientific Meeting 29 November 2019

Dear colleagues,

This is the second announcement of the CWI Scientific meeting, to be held *this* Friday, at 13:00, in the Turing room. Lunch will be provided beforehand. We have four Postdoctoral researchers speaking about a range of exciting topics, and you can find the program below. You are all cordially invited to attend!

Best wishes,
Abdallah and Jannis


Speaker: Joost Berkhout (IAS)

Title: Production Scheduling in an Industry 4.0 Era

Abstract: In this talk a modern industrial plant is considered that produces a large variety of composite biomaterials. Incoming orders are processed in real-time and slotted into a production schedule to meet the required delivery deadline. The scheduling problem is complicated because of numerous constraints, chief among them the limited storage capacity for intermediate or finished products and avoiding contamination between product runs. Solving this complicated scheduling problem currently requires comprehensive manual intervention by experienced planning experts. As a result, it is labor-intensive and lacks flexibility. Moreover, it misses the chance of utilizing the wealth of sensory production data in an industry 4.0 era to enhance the scheduling. This talk presents an algorithm that combines mixed integer linear optimization and evolutionary computing to solve the scheduling problem in the industry 4.0 setting.


Speaker: Irene Viola (DIS)

Title: Compression approaches for light field photography

Abstract: Since its invention in the 19th century, photography has allowed to create durable images of the world around us by capturing the intensity of light that flows through a scene, first analogically by using light-sensitive material, and then, with the advent of electronic image sensors, digitally. However, one main limitation of both analog and digital photography lays in its inability to capture any information about the direction of light rays. Through traditional photography, each three-dimensional scene is projected onto a 2D plane; consequently, little information about the position of the 3D objects in space is retained. Light field photography aims at overcoming these limitations by recording the direction of light along with its intensity. However, a considerably larger volume of data is generated when compared to traditional photography. Thus, new solutions must be designed to face the challenges light field photography poses in terms of storage, representation, and v!
 isualization of the acquired data. In particular, new and efficient compression algorithms are needed to sensibly reduce the amount of data that needs to be stored and transmitted, while maintaining an adequate level of perceptual quality.


Speaker: Christian Majenz (A&C)

Title: Hash functions in post-quantum cryptography

Abstract: Hash functions are ubiquitous in modern cryptography. Prominent applications include, e.g., digital signatures and active security for public-key encryption. In this talk, I will explain why hash functions security is arguably the most quantum aspect of post-quantum secure cryptography, and highlight some challenges, results and questions.


Speaker: Makrand Sinha (N&O)

Title: Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Abstract: I will talk about a central conjecture in communication complexity, called the log-rank conjecture and its variants for randomized and quantum communication. Chattopadhyay, Mande and Sherif (STOC 19) recently exhibited a total Boolean function disproving the randomized version of this conjecture. In joint work with Ronald de Wolf, we used tools from quantum information theory to show that the same function also disproves the quantum variant.

A more technical abstract is as follows:  Chattopadhyay, Mande and Sherif (STOC 2019) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture.

Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (Theory of Computing 2018) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method.