Software & CompSci

Papers

  • Attempting the impossible: Enumerating extremal submodular functions for n=6

    By Elod Csirmaz and Laszlo Csirmaz.

    Submodular functions have applications in such diverse areas as information inequalities, operational research, combinatorial optimization and social sciences, and they have also found fundamental applications in game theory and machine learning. Enumerating the extremal submodular functions defined on subsets of a fixed base set has only been done for base sets up to five elements. This paper reports the results of attempting to generate all such functions on a six-element base set. Using improved tools from polyhedral geometry, we have computed 360 billion of them, and provide the first reasonable estimate of their total number, which is expected to be between 1,000 and 10,000 times this number. We also present insights into the symmetries of these functions, as well as two new inequality insertion orders that allow processing them further than before.

    Available on arXiv ». The related code is available on GitHub ». The partial result set can be found on Zenodo ».

  • Computer Science
    Synchronizing Many Filesystems in Near Linear Time

    By Elod Csirmaz and Laszlo Csirmaz, in Future Internet 2023; 15(6):198.

    Finding a provably correct subquadratic synchronization algorithm for many filesystem replicas is one of the main theoretical problems in Operational Transformation (OT) and Conflict-free Replicated Data Types (CRDT) frameworks. Based on the Algebraic Theory of Filesystems, which incorporates non-commutative filesystem commands natively, we developed and built a proof-of-concept implementation of an algorithm which synchronizes an arbitrary number of replicas. It is provably correct, and has linear complexity after an initial sorting phase. It works by identifying conflicting command pairs and requesting one of them to be removed; can be guided to reach any of the theoretically possible synchronized states.

    Also available on arXiv ». See sample implementation of the filesystem synchronization algorithms on GitHub »

  • Computer Science
    Data Synchronization: A Complete Theoretical Solution for Filesystems

    By Elod Csirmaz and Laszlo Csirmaz, in Future Internet 2022; 14(11):344.

    Data reconciliation in general, and filesystem synchronization in particular, lacks rigorous theoretical foundation. This paper presents, for the first time, a complete analysis of synchronization for two replicas of a theoretical filesystem. While existing synchronizers are operation-based as they define, using some rationale or heuristics, how conflicts are to be resolved without considering the effect of the resolution on subsequent conflicts, our approach is declaration- based: we define what constitutes the resolution of all conflicts, and we prove the existence of sequences of commands which convert the replicas into a common synchronized state.

    All possible synchronized states are described by a partial order on the conflicts describing the order in which they need to be resolved, as well as the effect of each decision on subsequent conflicts. Using this classification, the outcomes of different conflict resolution policies can be investigated easily. Also available on arXiv »

  • Computer Science
    Algebra of Data Reconciliation

    By Elod Csirmaz and Laszlo Csirmaz, in Studia Scientiarum Mathematicarum Hungarica (26 Sep 2022).

    A paper on the algebra of data synchronisation which contains stronger and more rigorous results than before, and extends their scope to more data types. We investigate the algebraic properties of filesystem command sequence pairs that are applicable to the same data structure, and use these results to show that the reconciliation problem has a unique maximal solution. The syntactical properties of this solution also allow for an efficient algorithm to produce it. Also available on arXiv »

  • Diagram of neural network
    Interpreting Neural Networks by Reducing Nonlinearities during Training A short paper and sample code demonstrating a simple solution that makes it possible to extract rules from a neural network that employs Parametric Rectified Linear Units (PReLUs). We introduce a force, applied in parallel to backpropagation, that aims to reduce PReLUs into the identity function, which then causes the neural network to collapse into a smaller system of linear functions and inequalities suitable for review or use by human decision makers.
    Read the paper »
    More on GitHub »
  • Connected lightbulbs
    Remote Management in 9 Simple Steps: A Quick Practical Guide to Transitioning Away from the Office This note offers practical ideas to team leaders and managers who suddenly find themselves organizing the work of and managing their team remotely and are not entirely sure where to start.
    Read it in Management Matters »
  • Computer Science
    Algebraic File Synchronization: Adequacy and Completeness In this paper we investigate file synchronization. We define algorithms for update detection and reconciliation over an algebraic system of filesystem operations with high information content, and present rigorous proofs that they work as intended and cannot be improved on. Available on arXiv.org. More »
  • Computer Science
    An Algebraic Approach to File Synchronization Norman Ramsey and Előd Csirmaz, “An Algebraic Approach to File Synchronization,” in Proceedings of the Joint 8th European Software Engineering Conference and 9th ACM SIGSOFT Symposium on the Foundations of Software Engineering (New York: ACM Press, 2001), 175–185. More »
  • Computer Science
    A Transmission Protocol over the LP Port and , “Egy kommunikációs protokoll [A Transmission Protocol over the LP port],” in Híradástechnika /03, 42–46. We present and test a communication protocol using the line printer port with automatic synchronisation where bits or trits are transmitted as state changes.

Software

  • Superloop RNN models
    Superloop: Complex RNN Models A "superloop" is an extra loop that connects the output of a recursive neural network (RNN) back to its input in the next timestep via one or more external systems. This project contains: a framework to build RNNs with a superloop in TensorFlow/Keras, an implementation of a simple gated recurrent unit, an implementation of a register-based memory unit, and an implementation of an attention system that allows the network to move freely along the input data. More »
  • Trainable clustering
    Trainable Online Clustering Exploring recognizing unseen clusters with a neural network. Given an initial, labeled batch of data, we aim to train a system that is capable of classifying a stream of data and recognizing new classes it has not yet seen. More and get the code »
  • Image of PHP code
    PHP_Beautifier filters Filters for PHP_Beautifier that keep empty lines in the source, break argument lists and arrays into multiple lines, or change how assignment operators are spaced.
  • Part of NetArranger Screenshot
    NetArranger A JavaScript library that can arrange the nodes of a directed graph, network or diagram. Download or contribute to the source, or get the compiled library from GitHub, or check it out live in action.
  • ESFS logo
    ESFS A filesystem in C based on FUSE that supports snapshots. More »

More projects

  • openscad-py is a Python OOP precompiler for OpenSCAD's language.
  • nn_rnd_training trains neural nets using smart random walk without backpropagation (TensorFlow).
  • Manatee checks whether the expected values (means) of two samples are significantly different using bootstrapping.
  • ComfySQL is a PHP convenience class for MySQL databases.
  • SQLBrite is a PHP convenience class for SQLite3 access.

Earlier projects

Some old pieces of software for MS-DOS systems

Use the DosBox emulator to run these applications