Computer Science R&D and Teaching by Mircea Digulescu
Mircea Digulescu is an independent researcher in Computer Science. He never got financing for his activities, but is actively looking. His interests and publications are detailed below. He would like to identify partners to finance research and development up to products in each of the following areas:
· Cryptography. Mircea Digulescu is keen on Cryptography and has invented a novel cryptographic scheme based on a new technique he calls entropy enhancement. While not a mathematician, he is knowledgeable about the workings and fundamental security assumptions of most cryptographic schemes and protocols today. Also he is insightful about implementing and using cryptographic systems securely, avoiding common pitfalls like timing attacks, using low-entropy seeds, dictionary-based edit-distance attacks, using compromised machines to enter the secret key and more.
o In Pipeline: Functional Encryption: Turing-complete computation over encrypted data using SKREM-like ciphers (~2025?). The aim is to allow computations of arbitrary algorithms for a registry machine (which is Turing complete) over encrypted data, without knowing the decryption key. This would allow for scenarios where data can be uploaded to the Cloud in encrypted form, the cloud can perform some advanced operation without revealing the algorithm to the user, and finally send back the result to the user also in encrypted form. As a result, the Cloud processor never learns the data it processes, and also the end-user never learns the details of the advanced algorithm used. This idea is in development.
o In Pipeline: Light Reading on Cryptanalysis: automating breaking of substitution ciphers and recognizing plain texts (~2023). The purpose is to build a system which takes as input a text encrypted with a substitution cipher and efficiently outputs the plain-text. As ciphers become ever more sophisticated, this can be useful in brute force attacks on more sophisticated encryption, in cases where not enough of the original plain text is known. Ideas for the paper have been fully developed.
o In Pipeline: Irrefutable One-Time Cryptographic Digital Signatures based on SKREM-like ciphers (~2022). Signing short documents with a priory published, one-time public key, without making use of public key cryptography. This can be used to sign transactions on a block chain. Ideas for the paper have been fully developed.
o In Pipeline: Multilateral Secret Agent Recognition, Authorization and Coordination over a Public Channel based on a Shared Secret Key (~2022). Introduces a symmetric-key protocol for secret agents on the field to recognize each other over a public, monitored channel by simultaneously proving to each other knowledge of a shared secret, with zero-knowledge about it leaked to other observers on the channel. It also allows them to prove their rank to the most senior one on the field, without revealing it to others of lower rank than themselves. They can then also use this scheme to coordinate actions secretly. Unlike other schemes which rely on public key cryptography with prime factorization at its core making them vulnerable to attacks by quantum computers, this scheme relies on security of SKREM-like ciphers which are not vulnerable to quantum attacks. Ideas for the paper have been fully developed.
o In Pipeline: Secure Coin Flipping and Cryptographic Commit Protocol based on SKREM-like ciphers (~2021). Allows agents to commit to choosing a certain number without revealing it upfront. This in turns allows secure coin flipping. Unlike existing schemes whose security relies on prime factorization at its core, this scheme relies on security of SKREM-like ciphers. Ideas for the paper have been fully developed.
o In Pipeline: Super Simplified SKREM: Practicalizing Unbreakable Symmetric Key Encryption with Short Secret Keys (~2021). Introduces a simplified, practical variant of SKREM ciphers, based on the paper below, which has better algorithmic performance characteristics (number of random bits required, running time and memory complexity). Ideas for the paper have been fully developed.
o Completed: Hiding Data in Plain Sight: Towards Provably Unbreakable Encryption with Short Secret Keys and One Way Functions (2019 December). Introduces a novel symmetric key encryption scheme based on a technique of entropy enhancement based on the theory of algorithmically random sequences, by requiring up-front a large master table of random bits. Unlike existing schemes, it does not rely on the hardness of algebraic operations (such as the algebraic field inverse) but instead on that of indirection based on a random sequence. This scheme is called SKREM and is claimed to be provably unbreakable. See here or here.
o Existing Topics Known: AES (Rijandel), RSA, El-Gamal, Kerberos as well as basic Quantum Cryptography, Kolmogorov Extraction, Algorithmically Random Sequences, SHA, MD5, Merkel Trees, elementary Functional Encryption, interactive proofs.
· Complexity Theory and Computability.
o In Pipeline: Building Hard Cases for Hard Problems (~2024). Discover (perhaps automatically) cases for hard problems which cannot be easily solved using the techniques of the 2022-2024 papers or any other approaches.
o In Pipeline: How Intractable is Intractable: Solving Kolmogorov Complexity on the finite case (~2024). Discover (perhaps automatically) an algorithm which proves Kolmogorov complexity of short strings (up to 128 bits long? Or maybe 1024?) – or at least conveniently bounds it. Based on the techniques of the 2019-2023 papers.
o In Pipeline: Automatic SAT Solver (~2023). Discover (perhaps automatically) and a better 3-CNF-SAT solver than those in existence, based on the ideas presented in the 2019 paper.
o In Pipeline: Automatic Algorithm Finder (~2023). Refine and Implement the techniques from the 2019 paper to produce an algorithm which finds algorithms to solve hard problems. How fast will it find KMP, constant time 32- and 64- Bit Counting or A*? How about a good algorithm to efficiently factor 50 digit numbers?
o In Pipeline: Exact 3-CNF-SAT solver when there are many solutions (~2022). Exploiting the fact it is known that there are many solutions to a 3-CNF-SAT expression, finding one should be faster than in the general case.
o Completed: Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice (2019 November). Introduced the field of Finite Algorithmics: reasoning about problem difficulties for bounded inputs. Offered ideas and approaches for automatic and computer-aided discovery of algorithms for hard problems, on the finite case. Presented concrete directions for solving 3-CNF-SAT, Kolmogorov Complexity and Prime Factorization. See here or here.
o Completed: Nondecidability of Halting Problem – a Personal Proof (2013 September). Constructed a paradoxical computer program proving that there is no general-case solution for the Halting Problem. See here.
o Existing Topics Known: Finite Automata, Push Down Automata, Theory of Computing, Amortized Analysis, Master Theorem, Akka-Bazzi method, Intractability, Complexity Classes, NP-Completeness, Arithmetical Hierarchy, Quantum Computing, P-Spiking Systems, Bioinformatics (wrt Computability), Random Turing Machines, etc.
· Game Theory.
o In pipeline: Collusion with Binary Objectives in the Stable Marriage Problem (~2023). Continues the exploration of the 2021 paper, with a slightly modified objective function: the boys can either get a particular match or better or otherwise they are fully indifferent as to their individual outcome. Ideas for the paper have been almost fully developed.
o In pipeline: Resiliency by Design: Using Game Theory to structure organizations to withstand infiltration and treason (~2023). Addresses how to structure organizations into groups and loyalty thresholds based on individual outcome and trust in order to withstand poaching and infiltration. Idea is in development.
o In pipeline: War Games: Withstanding and Winning Protracted Conflicts using Game Theory (~2022). Deals with the concept of balancing production and spending with active military operations in order to withstand and win conflicts spanning a long period of time (such that war material is constantly being produced and churned). Idea is in development.
o In pipeline: Mosquito Drone Strike: Attack and Defense versus a Swarm of Drones (~2022). Expands upon the paper below to deal with the case where missiles can travel backwards in space. Idea is in development.
o In pipeline: Hold the Line: Missile versus Interceptor duels and the k-servers problem (~2022). Deals with identifying the best strategy for a massive missile attack and the corresponding best response on the defense side. Idea is in development.
o In pipeline: Survival and Prosperity: Multi-Currency Investment Strategy with forced spending (~2022). Deals with determining the optimal strategy for reaching an objective over a period of time starting with an initial capital across multiple currencies and choosing the most adequate investments for this purpose. Idea is in development.
o In pipeline: Threats and Bribes in the Stable Marriage Problem (~2021). Expands upon the 2019 and 2016 papers to the case where boys are willing to take risks of a worse outcome in order to issue ultimatums to one-another before game play so as to obtain a better match in case their threats work. Paper discusses the general structure of this new ultimatum problem and proposes an algorithm for identifying a reasonable strategy under a specific model. Ideas for this paper have been fully developed.
o In pipeline: Applications of the Stable Marriage Problem (~2021). Introduces a series of problems which can be formulated appropriately in terms of Stable Marriage Problem, including the likes of Vendor versus Contracting Authority, where an oligopoly of vendors colludes to get the best prices and projects from a number of accepting customers. Ideas for this paper have been fully developed.
o Completed: Weakening Nuclear Posture can result in added security (2019 Feb). Brief note on how certain combinations of doctrines lead to war, while weakening that of just one actor can result in peace. See here (in Romanian).
o Completed: Farsighted Collusion in Stable Marriage Problem (2019 May). Presented an efficient algorithm for computing the unique farsightedly stable boy-optimal matching in the Stable Marriage Problem. Also criticized earlier work pertaining to the subject and presented a few connected interesting results. The large body of the work is an independent rediscovery of results by Jun Wako (2010), adding upon them further details (a full implementation) of the efficient algorithm and structuring the proofs in a language more attuned for computer scientists (versus mathematicians), requiring fewer theoretical prerequisites. See here, here or here.
o Completed: Strategic Play in Stable Marriage Problem (2016 Aug). See here or here. Discussed in a very rough form a host of results pertaining to the Stable Marriage Problem, including applications thereof.
o Completed: Dealing it multiple times does not change the expected value (2015 May). Discusses how the common practice of dealing the turn and/or river multiple times in holdem poker games does not change the player’s expected value. Implies that random samplings of this type can be performed without substitution (applicable in A/B tests). The proof involved two innovative steps. See proof here and here and code sample here and here.
o Completed: Project: Success Probability Calculator (2015 April). Presents the implementation of an O(n*m) method for identifying the optimal investment strategy to achieve a target single-currency bankroll starting with some capital, choosing one of m investment options over n time periods. The project involved using of some more advanced data structures such as an efficient LRU cache implementation and a Space vs. Time Tradeoff Structure. See details here and source code here or here. The code sample includes an efficient LRU Cache implementation and other helper structures.
o Completed: Choosing a Gamble with Best Expected Value is often a bad strategy in Stochastic Games (2014 Aug). Argued by example that this is the case. See details here (in Romanian).
o Completed: A Game of Ultimatum – Surprising Results of Rational Play (2013 Dec). Inspired by a 2013 lecture by negotiation expert Moty from Moscow School of Management SKOLKOVO, a particular 3-player general-sum game of ultimatum was examined, leading to surprising results. See details here (in Romanian).
o Existing Topics Known: Two/Many Player Zero-Sum Games, General Sum Games, Kernel of a Game, Nash Equilibrium, Discrete Stochastic Games, Sprague-Grundy Numbers, some intractability results, etc.
· Algorithms and Data Structures.
o In pipeline: Adaptive Topology in Distributed Solving of Sorting Problems (~2023). Introduces a O(m*log n) network time + O(n*log^2 n) external time method for distributed sorting, involving a dynamic, adaptive network topology. While the O(m*log n) bound is matched much simply by the MM algorithm using sorting networks, the approach of adaptive topology is judged to be of general interest and the method is presented as an inspiration for other researchers to examine this kind of approach. Ideas for this paper have been fully developed.
o In pipeline: Sub-linear Time Routing in Urban Networks (~2023). Introduces an efficient method, based on smart precomputation to support queries of the form “shortest path from A to B” in graphs representing Urban Networks, which should run much faster than Dial’s algorithm and A*.
o In pipeline: Memory Efficient Van Emde Boas Data Structure (~2023). Combines a vEM Tree with a Universal Perfect Hashing scheme to obtain an expected time O(log log U) INSERT / DELETE / FIND / UPDATE / MIN / MAX / PREDECESOR / SUCCESOR data structure with only O(n) memory for n queries of keys in the universe 0..U. This improves on vEM Trees in terms of memory consumption from O(U) to O(n).
o Completed: Shortest Path in a Weighted Graph with Small Edge Costs (2003, GInfo). An independent rediscovery of Dial’s algorithm O(V+E*C) and the brief presentation of a method to further reduce complexity to O(V+E*log log C) using a vEM Tree. Neither Mircea Digulescu, nor the reviewer from GInfo, were aware of Dial’s algorithm at the time (which is so obscure in literature that finding it on Google Scholar is still unsuccessful as of Feb 2021).
o Completed: Kirkpatrick’s Algorithm (2003, Ginfo, with Andrei Matei coauthor). Presented the famous Kirkpatrick Algorithm and Data Structure for efficient point location in the plan using successive triangulations.
o Other independent rediscoveries: Kosaraju’s Algorithm, Fisher Yates Shuffling Algorithm.
o Existing Topics Known: Mircea Digulescu is a recognized as an expert on Algorithms and Data Structures. He is familiar with the following: AVLs, KD-trees, Interval and Segment Trees, B-trees, AB-trees, Orthogonal Range Queries with Fractional Cascading, RMQ, LCA, Binary Heaps, Binomial Heaps, Fibonacci Heaps, Universal Perfect Hashing, Disjoint Sets, KMP, Rabin Karp, Dijkstra, A*, Bellman-Ford-Moore, Floyd-Warshall, Dial, Egg Dropping, Network Flow – Floyd-Fulkerson and Lift to Front, Paxos and many, many others. Also, besides knowing and understanding these algorithms (some of which he independently discovered while reading Cormen CLRS when he was 15-17 yo), he is well apt to apply them, with a vast industry experience and over 320 problems solved on Codeforces.com, where he is a Div1 coder: mircea85. Additionally he solved many non-research problems from the Cormen CLRS and Knuth TAOCP computer science books.
Besides being interested in obtaining financing to continue research as per his interests above, Mircea Digulescu is also interested in partnering with someone for coauthorship publication (in recognized peer-reviewed journals), Translation of results in another language and Dissemination of said to appropriate recipients, with proper attribution.
Mircea Digulescu is also apt to teach or train on topics including advanced Computer Science, both based on his own research interests and results, as well as at the Master’s (for example covering the material of MIT Advanced Data Structures) and at the Bachelors’ levels (for example covering MIT Introduction to Algorithms or the entirety of Cormen CLRS book, including exercises). Additionally he can teach or train on Software Engineering, including writing clean and maintainable code, fundamental DevOps, code reviews, architectural and design patterns and building or using Cloud services, like AWS SQS or Redis.
Mircea Digulescu’s computer science and education credentials include:
· Div1 coder on www.codeforces.com – roughly in Top 0.3% best of the best coders of all time world wide - http://codeforces.com/profile/mircea85 - highest score 2022, candidate master, with over 320 problems solved (NB: I continue training here, so current rating can vary).
· Codility Golden Award for the Calcium 2015 Challenge – 2015 – see here.
· 10th place at the ACM ICPC Southeastern Regional Contest - 2005
· 4th place at the ACM ICPC Southeastern Regional Contest – 2004
· 1 Bronze Medal at European International Olympiads in Computer Science (CEOI) - 2004
· 1 H. Mention at European International Olympiads in Computer Science (CEOI) - 2003
· 3rd prize at the Romanian National Computer Science Olympiad – 2004
· 3rd prize at the Romanian National Computer Science Olympiad - 2003
· Multiple prizes at other lower-level Computer Science and Mathematics Olympiads and contests
Teaching Experience and Education:
· University of Bucharest - Faculty of Mathematics and Computer Science – Doctoral Studies in Applied Computer Science – 2014 - 2019 PhD (ABD) completed. Main contributions related to Stable Marriage Problem and to Distributed Sorting. I encountered heavy resistance at getting my work published in indexed peer-reviewed journals – for matters of form - not lack of correctness or relevance, which lead to delays. Finally, in summer of 2019, after completing all work except dissertation, I withdrew from the PhD program in order to get my diplomas. I thus graduated ABD – all but dissertation (for which indexed publications were required).
· Trainer at Academia Credis (IT Training) –Java Basic (2017): I taught the Java Basic course to a class of about 15 adult students as a side job, more out of passion and my desire to learn Java as well. This was an on-site, in person project, during evenings. I earned 1000 EUR for the month-long course.
· Assistant Professor at University of Bucharest - Faculty of Mathematics and Computer Science ( Romania’s top University - http://fmi.unibuc.ro/) (2014): I taught Object Oriented Programming (OOP, C++) and Formal Languages and Automata (LFA) courses, holding lectures, providing hands-on assistance, creating and handing-out workouts, providing written and oral feedback and generally developing specified aptitudes. I had a great time and all of my students got excellent industry positions later on. I had a great time teaching. I earned about 350 Euros / month while working here.
· Train of Trainers Course (2014) at Frends. Completed this program at the invitation of a friend at the time. Frends is a volunteering non-profit, associated with University student groups and student life.
· National Students’ Congress (2013) – Palace of Parliament (Bucharest) – Speaker. I blabbered a bit about some irrelevant educational topics. Was invited there by surprise.
· Softbinator Tracing the Roadmap Conference (2012) – Romanian National Library (Bucharest) – Speaker. I spoke on topics of Entrepreneurship and explained the value in having a vast number of autonomous economic actors, versus dealing with an oligopoly.
· University of Bucharest - Faculty of Mathematics and Computer Science – Master’s Degree Software Engineering (2008-2010). Dissertation thesis “Resource Sharing in a multi-process, multi-transaction environment”, Merit scholarship during 1st year.
· University of Bucharest - Faculty of Mathematics and Computer Science – Bachelor’s Degree Computer Science (2004 – 2008). License thesis “CryptoSafe” – a WinRar desktop application which encrypts data with AES instead of compressing it. Merit scholarship during 1st year.
· National Computer Science High-school “Tudor Vianu” – Baccalaureate, High-school Degree – (2000 – 2004). During high school I joined fashion of taking SAT tests (1400 SAT1, 1800 SAT2 Math IIC, 1730 SAT2 Physics) and applying to US University, and I was offered admission at Cornell University but never joined - declined eventually due to financials mainly.
· See further relevant details in Section 2 of the Presentation Page.
See Mircea Digulescu’s publications and profile on Academia.edu here and on arXiv.
Mircea Digulescu also has the competence to teach or train on topics of Leadership, Strategy, Intelligence, Business Administration, Organizational Architecture, as well as others.